WHUoj 1603 Minimum Sum

秒速五厘米 2022-07-27 11:56 148阅读 0赞

题目链接：  
[http://acm.whu.edu.cn/land/problem/detail?problem\_id=1603][http_acm.whu.edu.cn_land_problem_detail_problem_id_1603]

题意：给你n个数，你要从n个数中挑选m个数，使m个数中的所有的不同的两个数的差的绝对值之和最小（只要一个数不同两个数的组合即为不同）

题解：我们先将n个数排序，m个数一定是n个数中连续的一段，因为假如不是连续的，一定能找到一个连续的比它小，关键是如何在0(n)的时间中找到这一段数  
我们可以用前缀和，假设前i个数的和为sum\[i\]，第i个数与前其前m-1个数的差的等于  
a\[i\]\*(m-1)-(sum\[i-1\]-sum\[i-m\])  
我们接下来就可以先求出前\[1,m\]个数的差的和，然后最后一项每次向后移动一位，第一项每次也向后移动一位，枚举完所有区间即可,时间复杂度为O（n）。

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    LL a[100005];
    LL summ[100005];
    int main()
    {
        int n,m;
        while(RII(n,m)!=EOF)
        {
            for(int i=1;i<=n;i++)
                RI(a[i]);
            sort(a+1,a+n+1);
            mem(summ);
            for(int i=1;i<=n;i++)
            {
                summ[i]=a[i]+summ[i-1];
            }
            long long int ans=inf;
            LL ans1=0;
            for(int i=2;i<=m;i++)
                ans1+=a[i]*(i-1)-summ[i-1];
    
            ans=min(ans1,ans);
            for(int i=m+1;i<=n;i++)
            {
                ans1+=(m-1)*a[i-m]+summ[i-m]-summ[i-1];
                ans1+=summ[i-m]-summ[i-1]+(m-1)*a[i];
                ans=min(ans,ans1);
            }
            printf("%lld\n",ans);
    
        }
    
        return  0;
    }

[http_acm.whu.edu.cn_land_problem_detail_problem_id_1603]: http://acm.whu.edu.cn/land/problem/detail?problem_id=1603