Codeforces 1175D Array Splitting

1175D

You are given an array a1,a2,…,an and an integer k.

You are asked to divide this array into k non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let f(i) be the index of subarray the i-th element belongs to. Subarrays are numbered from left to right and from 1 to k.

Let the cost of division be equal to . For example, if a=[1,−2,−3,4,−5,6,−7] and we divide it into 3 subbarays in the following way: [1,−2,−3],[4,−5],[6,−7], then the cost of division is equal to 1⋅1−2⋅1−3⋅1+4⋅2−5⋅2+6⋅3−7⋅3=−9.

Calculate the maximum cost you can obtain by dividing the array a into k non-empty consecutive subarrays.

Input
The first line contains two integers n and k (1≤k≤n≤3⋅105).

The second line contains n integers a1,a2,…,an (|ai|≤106).

Output
Print the maximum cost you can obtain by dividing the array a into k nonempty consecutive subarrays.

翻译：有一个数列，现在我们把数列分成k组，每组至少一个数，函数是所属的那一组的组数，比如属于第2组，。
现在考虑代价函数，求它的最大值。

解法：很直观的一个想法就是我们把尽量把大的排在后面，这样可以让尽可能的变大，所以我们想到贪心算法，同时考虑到这道题是按照顺序划分组数，由此我们考虑计算它的个部分和，对这n-1个部分和进行排序，最小的那个我们要排在最前面
最后该如何写出的表达式呢？现在我们已经有了个按照顺序排列好的部分和，我们注意到假设第一个部分和含有，那么后面的部分和至少都含有，考虑，对于个部分和的前个来说，如果我们用减去前个部分和，我们就得到了的系数，如果然后我们把从序列中丢掉，因为所有的都少了所以不影响整体的排序，如法炮制我们可以确定的系数，同理我们通过前的部分和把的系数全部确定下来，同时不难证明系数组成的序列是不减的。下面我们来证明现在我们得到的序列(是确定的系数)是让代价函数最大的序列。
证明：如果存在一个序列使得代价函数的值更大， 那么不妨设这个序列为，我们设第一次和不同的下标为，那么必然大于，且，因为系数序列是不减的也是连续的，这相当于在前个部分和中，出现的次数比原来少了一次，因为只考虑前个部分和中每项出现的次数的时候其实属于这些部分和出现的顺序无关的，所以出现次数变少，只能是某个包含的部分和不属于前中，但是又不能改变其最小性，这表明有部分部分和是一样的，且这些部分和一直相等到最后几项，超过了的界限，这表明有一些项的和是0，把这些项看成一个项，再次进行上述的构造的过程就会产生矛盾。
代码如下

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
long long n, k, ans, x, a[N];
int main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) 
        scanf("%lld", &x), a[i] = a[i - 1] + x;
    ans = a[n] * k;
    sort(a + 1, a + n);
    for (int i = 1; i < k; i++) ans -= a[i];
    printf("%lld\n", ans);
    return 0;
}