2017湘潭大学邀请赛E题（贪心）

链接：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;

}

巴特西

2017湘潭大学邀请赛E题（贪心）

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

Partial Sum

Input

题意：

题解：

最新文章

热门文章