Cut题解
Cut
http://www.nowcoder.com/questionTerminal/3c3c48bcf3e446ca92c74e0133bba2d0
一开始看其实题目挺简单的,贪心策略很简单,只需要把得到的数组升序排列,然后分别算出第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; }