https://www.luogu.com.cn/blog/516346/solution-at-abc252-f

闲话

原题 P1334 瑞瑞的木板。刚好不久前做过，赛时直接贺了自己的代码过掉的。

题目翻译

为方便和瑞瑞的木板联系起来，下文翻译不采用原题中的“面包”而是使用“木板”。

有一根长度为 $L$ 的木板，切成 $n$ 根小木板。第 $i$ 根小木板的长度为 $l_i$，每次切下长度为 $x$ 的小木板需要耗费 $x$ 的体力。允许有剩余，也就是说不保证 $L=\sum_{i=1}^n l_i$。

题目思路

本题与瑞瑞的木板唯一区别，即不保证 $L=\sum_{i=1}^n l_i$。为了方便我们贺代码，我们可以自己加一块长度为 $L-\sum_{i=1}^n l_i$ 的木板。这时耗费体力肯定不变。

那么这题就完美的变成了瑞瑞的木板。接下来，我们按照合并果子的贪心思想，每次切最小的即可。详细的贪心证明可以去看 P1090 合并果子 的题解。

完整代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	multiset<long long>s;
	long long n,l,ss=0;
	cin>>n>>l;
	for(int i=1;i<=n;i++)
	{
		long long x;
		cin>>x;
		s.insert(x);
		ss+=x;
	}
	if(l-ss!=0)s.insert(l-ss);//插入新的小木板
	long long sum=0;	
	while(s.size()>1)
	{
		long long x=*s.begin();
		s.erase(s.begin());
		long long y=*s.begin();
		s.erase(s.begin());
		s.insert(x+y);
		sum+=x+y;
	}
	cout<<sum<<endl;
	return 0;
}