CF1175D Array Splitting(贪心思维+前缀处理)

洛谷评测地址：https://www.luogu.com.cn/problem/CF1175D

解析:

假设这k段为：[p1,p2][p3,p4].......[pk-1,pk]

令S表示前缀和

则有

all

==Sp1+2*(Sp2-Sp1)+3*(Sp3-Sp2)......k*(Spk-Spk-1)

==-Sp1-Sp2-Sp3.....+k*Spk

==-(Sp1+Sp2+Sp3....+Spk-1)+k*Spk

所以记录前缀和，把前k-1小的前缀和带入上述公式即可。

但是注意一点，上式子的Spk，其实就是Sn，是不能变的，是一定要*k的。所以在排序的时候，只需要排前n-1个前缀和。

即：sort(sum+1,sum+n);

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5 + 5;
int a[maxn];
ll sum[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    sort(sum+1,sum+n);
//    for(int i=1;i<=n;i++)
//        cout<<sum[i]<<" ";
//        cout<<endl;
    ll ans=0,cnt=0;
    for(int i=1;i<k;i++)
        ans+=sum[i];
    cout<<k*sum[n]-ans<<endl;
}