2017湘潭大学邀请赛E题(贪心)

时间:2021-12-13 23:18:48

链接:https://www.icpc.camp/contests/4mYguiUR8k0GKE

                                           Partial Sum

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case: The first line contains three integers n, m, C. The second line contains n integers a1, a2, . . . , an.

• 2 ≤ n ≤ 105

• 1 ≤ 2m ≤ n + 1

• |ai |, C ≤ 104

• The sum of n does not exceed 106 .

题意:

给出n个数,每次选连续的一段数,已经被选作起点或终点的点不能再被选作起点与终点。

题解:

由于是绝对值  ,|sum|=max(cal[a]-cal[b],cal[b]-cal[a]);

而贪心的做法是将所有前缀和+0,共n+1个元素进行排序。

每次取出最大值和最小值相减即为最优解

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int cal[maxn];
int main()
{
    int n,m,C;
    while(cin>>n>>m>>C)
    {
        cal[0]=0;
        for(int i=1;i<=n;i++)
        {
            int num;
            scanf("%d",&num);
            cal[i]=cal[i-1]+num;
        }
        sort(cal,cal+1+n);
        long long ans=0;
        for(int i=1;i<=m;i++)
        {
            int kk=abs(cal[i-1]-cal[n-i+1]);
            if(kk<=C)break;
            ans+=(kk-C);
        }
        cout<<ans<<endl;
    }
    return 0;
}