Cut题解

一开始看其实题目挺简单的，贪心策略很简单，只需要把得到的数组升序排列，然后分别算出第1项到第n项和，第2项到第n项，......第n-1项到第n项和，全部加起来。
为什么呢？因为题目说的是获得最大的分割代价，而分割一次的代价是（剩余）原序列的和，那我们只需要让比较大的数多做贡献，就可以了，也就是说完成输入后，从小到大分割即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100010]={0};
int main(){
    int n,i=0,j;
    long long ans=0;
    cin>>n;
    while(i<n){
        scanf("%d",&a[i++]);
    }
    sort(a,a+n);
    for(i=0;i<n-1;++i){
        for(j=i;j<n;++j){
            ans+=a[j];//按照前面所述的，加起来
        }
    }
    cout<<ans<<endl;
    return 0;
}

超时了，后来一分析，不对劲，双重循环O(n^2)的复杂度，很多操作重复了，于是改成下面这个，就AC了

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100010]={0};
int main(){
    int n,i=0;
    long long ans,sum1,sum2;
    ans=sum1=sum2=0;
    cin>>n;
    while(i<n){
        scanf("%d",&a[i]);  //用scanf在大规模读取时，会稍稍快点
        sum1+=a[i++];  //先把数组总和加起来，后面会快一些
    }
    sort(a,a+n);
    for(i=0;i<n-1;++i){  //分割只需要 n-1次，这个是O(n),比前一种的O(n^2)快,总复杂度为O(n*logn)
        ans+=sum1-sum2;
        sum2+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}