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

所以想一想暴力策略,就是选出所有牌堆中最少的那一堆,用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;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *