1,这题它自己都觉得奇特。。
2，咱也不急的看懂一步步来。
#include<iostream> using namespace std; const int maxn=1005; int n; int a[maxn]; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; long long ans=0; while(n>1) { int min1=0,min2=1; if(a[min1]>a[min2]) swap(min1,min2); for(int i=2;i<n;i++) { if(a[i]<a[min1]) { min2=min1; min1=i; } else if(a[i]<a[min2]) { min2=i; } } int t=a[min1]+a[min2]; ans+=t; if(min1==n-1) swap(min1,min2); a[min1]=t; a[min2]=a[n-1]; n--; } cout<<ans<<endl; }
4，有点奇怪有点不懂，感觉也没有排序。
5，放心很快就费大费小了。
我不怎么能想出来并想清楚。因为自由切割让你挺难受。但是你可以借鉴二叉树的思维。我们把它分来分去，我们发现了一些可贵的品质，比如叶子的深度×叶子代表的数，之后我们发现如果我们想要到达一个最小花销的情况我们必须，嗯，最短的板和次短的板是兄弟节点。
嗯发现了这个性质之后那就好办了，我们找出最短和次短的板，当成最后一次的切，切出了它们，那么我们把它合并上去，同理递推地进行这个操作。
费大，一是建模型，二是类比那是这个啥。。。
确实有贪心，即单一维度下的评测。这个的单一维度就是最短的板
但是切这个确实有二分性。二分性和二叉树呵呵。
这个还是建立模型吧，其实也可以反向思考，给你一些分开的木板，要全部弄到一块，但是你每次只能连两个木板。并且每次连两个木板的代价是这个两个木板长度之和。然后每次就连最短的和次短的行不。对的
这个是不是可以写个证明什么的。想起了合并果子哈哈哈哈啊。这个可以记一下。。。至于类比？？？
至于代码细节，那你得手推。但是这个样例比较简单。。分析不出来啥。。
#include<iostream> using namespace std; int n,a[1005]; long long ans=0; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; while(n>1) //为什么要n>1好好考虑了嘛？ ,这个就是那个递归嘛 { int min1=0,min2=1; if(a[min1]>a[min2]) swap(min1,min2); for(int i=2;i<n;i++) { if(a[i]<a[min1]) { min2=min1; min1=i; } else if(a[i]<a[min2]) { min2=i; } } int t=a[min1]+a[min2]; ans+=t; if(min1==n-1) swap(min1,min2);//也就是的意思是这次找最小的话 //刚好是最后一个，因为下面是先把t的值赋给a[min]，要是这样的话，a[n-1]就没东西了 //所以选择这样的。但我觉得有点牵强。 //不是说这个，而是整个代码宏观上的 //只差这一个了 a[min1]=t; a[min2]=a[n-1]; n--; //靠终于懂了n-1是因为上面把a[min2]=a[n-1] } cout<<ans<<endl; }
10，再 就是改变后的了，
sort排序默认是从小到大的。
#include<iostream> #include<algorithm> using namespace std; int n,a[1000005]; long long ans=0; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; while(n>1) { sort(a,a+n); int min1=0; int min2=1; int t=a[min1]+a[min2]; ans+=t; a[min1]=t; a[min2]=a[n-1]; n--; } cout<<ans<<endl; }
唯一的缺点是过不了大数据
因为你用的是sort.