饼干
先看看没有魔法饼干怎么做,我们一定是吃一个然后补满然后最后一次补到剩下的所有值，接下来就直接吃完
考虑我们减少了多少，一个饼干的花费可以看成一个1到 \(a_i\) 的数列，我们减少的一定是几个数列的整块和一个数列的前缀，因此我们选大的一定不劣
现在有魔法饼干相当于给几个数列减去最大值，容易贪心减最大值
现在把这两个拼起来，考虑怎么做，不难发现操作一是从最小值减到最大值，而操作二直接减去最大值，因此我们先进行操作一，再次进行操作二即可，复杂度 \((n\log n + m)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N = 1e6 + 7;
ll ans ;
int n , m , mm , k;
int a[N],L,R;
multiset<int>s;
int b[N];
signed main()
{
cin >> n >> m >> k;mm = m;
for(int i=1;i<=n;i++) cin >> a[i],s.insert(a[i]);
while(s.size()&&m)
{
auto x = *s.rbegin();
s.erase(s.find(x));
int val = min(x,m);int xx = x;
x -= val;m-=val;
if(x) {
b[xx]++;b[val]--;
break;
}
}
for(auto v:s) b[v] ++ ;
for(int i=mm;i>=1;i--) b[i] += b[i+1];
for(int i=mm;i>=1;i--){
int val = min(b[i],k);
b[i] -= val;
k -= val;
}
for(int i=1;i<=mm;i++){
ans += 1ll * i * b[i];
}
cout << ans;
}