【题解】扑克牌 贪心 bzoj1816 ——litble

我们发现，拥有的牌的种类越多，对我们越有利。

所以想一想暴力策略，就是选出所有牌堆中最少的那一堆，用 Jocker 代替，否则取一张，不断进行本操作。

而你发现这样取着取着，就会有很多牌堆里的牌张数一样了，并且一定是初始最少的牌的张数会变得一样。

假设前 $i$堆已经变得张数一样了，那么我们考虑在前 $i$堆每一堆上加一张 Jocker，然后取 $i$次将加进去的 Jocker 取完，这叫做一组操作。每做完一组操作，前 $i$堆各少 $i-1$张牌，后 $n-i$堆每堆少 $i$张牌，所以做 $c_{i+1}-c_i$组后，前 $i+1$堆的牌张数就一样了。

于是我们这么贪心的取即可，当然取的过程中，可能因为两个限制无法正好做 $c_{i+1}-c_i$组操作，一个是 Jocker 的数量，一个是前 $i$堆每堆的牌的数量。

做完这些一组一组的操作后，再做每一堆取一张。所以你发现，假设最终受到限制导致只能做 $k$组，做完 $k$组后还剩一些 Jocker，如果继续使用它们，并不能使答案更优，所以剩的那些 Jocker 也不用使用了。当然如果一直做到所有牌堆的牌数都相同了还有剩的 Jocker，当然要用掉。

复杂度 $O(n \log n)$，时间瓶颈在排序。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int inf=0x3f3f3f3f;
int n,m,ans,orz,c[55],s[55];//s: 差分记录牌的减少情况
int main()
{
    scanf("%d%d",&n,&m);
    for(RI i=1;i<=n;++i) scanf("%d",&c[i]);
    sort(c+1,c+1+n);
    for(RI i=1;i<n;++i) {
        int d=c[i+1]-c[i];
        if(d*i>m-ans) {
            int k=(m-ans)/i;
            if(d*(i-1)>c[i]-ans) k=min(k,(c[i]-ans)/(i-1));
            ans+=k*i,s[1]-=k*(i-1),s[i+1]+=k*(i-1),s[i+1]-=k*i;break;
        }
        else if(d*(i-1)>c[i]-ans) {
            int k=(c[i]-ans)/(i-1);
            ans+=k*i,s[1]-=k*(i-1),s[i+1]+=k*(i-1),s[i+1]-=k*i;break;
        }
        s[1]-=d*(i-1),s[i+1]+=d*(i-1),s[i+1]-=d*i;
        ans+=d*i;
    }
    orz=inf;
    for(RI i=1;i<=n;++i) s[i]+=s[i-1],c[i]+=s[i],orz=min(orz,c[i]);
    int k=min((m-ans)/n,orz/(n-1));
    ans+=k*n,orz-=k*(n-1);
    printf("%d\n",ans+orz);
    return 0;
}