题解 CF1175D 【Array Splitting】

思维题

当时比赛时一看到题还以为是dp，后发现不对。

观察这题有什么奇怪的特征，就是每段乘的数是一次加1的。

考虑一段区间比如说是形如:2A3B,现在要使这段区间整体后移一位，就变成了:3A4B。发现就是加上了一个区间和sum。

那么答案可以看成k段后缀区间的和（注意区间1-n是一定要的）

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,k,ans,a[N],b[N];
multiset<int,greater<int> >s;
multiset<int,greater<int> >::iterator it;
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);    
    for(int i=n;i;i--)b[i]=b[i+1]+a[i];
    b[1]+=1e15;
    sort(b+1,b+n+1);
    for(int i=n;i>=n-k+1;i--)ans+=b[i];
    int x=1e15;
    printf("%lld",ans-x);
    return 0;
}