题目大意：
输入N ( 1 ≤ N ≤ 20,000 ) ；将一块木板分为n块
每次切割木板的开销为这块木板的长度，即将长度为21的木板分为13和8，则开销为21
接下来n行描述每块木板要求的长度L ( 1 ≤ L ≤ 50,000 )
木板长度恰好等于各段木板长之和
Sample Input
3
8
5
8
Sample Output
34
挑战上的一个奇妙的贪心的方法
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,L[];
int main()
{
while(~scanf("%d",&n))
{
memset(L,,sizeof(L));
for(int i=;i<n;i++) scanf("%d",&L[i]);
ll ans=; /// 从结果L[]倒推
while(n>)
{
int i0=,i1=; // 维护最小段和次小段的下标
if(L[i0]>L[i1]) swap(L[i0],L[i1]);
for(int i=;i<n;i++)
if(L[i]<L[i0]) i1=i0,i0=i;
else if(L[i]<L[i1]) i1=i; int tmp=L[i0]+L[i1];// 将两段合并
ans+=(ll)tmp; // 开销为长度 /* 舍弃L[i0]和L[i1] 并将合并后的tmp保存在L[]中
就是总共只舍弃一段
而因为段数n随着合并会不断缩小
所以把要舍弃的一段放在n-1的位置即可 *若i0或i1有一个为n-1 则让i1为n-1
将tmp放在i0中 i1舍弃
*若i0和i1都不为n-1 则L[n-1]是需要被保留的
将tmp放在i0中 L[n-1]放在i1中
*/
if(i0==n-) swap(i0,i1);
L[i0]=tmp; L[i1]=L[n-];
n--;
}
printf("%lld\n",ans);
} return ;
}
可以借助优先队列高效实现
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int main()
{
while(~scanf("%d",&n))
{
priority_queue <int,vector<int>,greater<int> > q;
for(int i=;i<n;i++)
{
int m; scanf("%d",&m);
q.push(m);
}
ll ans=;
while(q.size()>)
{
int i0=q.top(); q.pop();
int i1=q.top(); q.pop();
int tmp=i0+i1;
ans+=(ll)tmp; //printf("%d %d %lld\n",i0,i1,ans);
q.push(tmp);
}
printf("%lld\n",ans);
} return ;
}