闲话

原题 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;
}