题解：P10971 Cookies

· · 题解

提供一个能卡过，甚至能到最优解，不用 dp 的暴力乱搞做法。

其他题解说的很清楚了，每个人分配到的饼干个数随 g_i 递增。

下面我默认先强制给每个人分一个然后令 m=m-n，这样可以取到 0。

我们先按 g 降序，按所有人分配到的饼干的个数的个数分类讨论。

1. 所有人可以分配一样多

这种情况显然答案为 0，判定条件是 m\equiv 0\pmod n。

2. 一共有两种不同个数

当 \lfloor \dfrac{m}{n-1}\rfloor\ge m\bmod (n-1) 时，我们可以，给前 n-1 个分配 \lfloor \dfrac{m}{n-1}\rfloor 个，给最后一个分配 m\bmod (n-1) 个。

考虑满足不这个条件的 m 的上界，由于 m\bmod (n-1)\le n-2，则有 \lfloor \dfrac{m}{n-1}\rfloor\le n-1，所以 m\ge (n-1)^2+(n-2)=n^2-n+1。

这样，我们把 m 在 O(n^2) 以上的情况干掉了，后面的 O(m) 与 O(n^2) 同级。

3. 一共有 3 种不同个数

不难发现，把最小的个数全都清零分配到大的从而多造几个最大值显然更优，所以最小值一定是 0，但考虑到会有剩下一部分饼干的情况，可能会出现一个次大值，也就是说，我们最优策略是尽可能多造最大值，同时还可以发现，我们还要尽可能减少非最大值，于是我们可以直接枚举有多少个最大值，为了确定最大值具体是几，我们还得多枚举一下最大值或者次大值的值，多少个 0，0 的个数从小到大枚举，只要搜到就停。

另外考虑到一些奇怪的奇偶性和边界的问题，次大值可能不止一个，但最多有两个，这个结论我没证出来，但我经过了又臭又长的巨型分讨后证明了在数据范围内是成立的，所以我们要把有一个次大值和两个的情况分别枚举。

分析一下时间复杂度，最后一种情况是瓶颈，所以只分析这一种就行，我们要枚举有多少个最大值这个是 O(n) 的，多少个次大值，由于次大值的个数只有两种可能，所以是 O(1) 的，还要枚举最大值或者次大值的具体值，只需要枚举一个就行，另一个可以算出来，这个是 O(m) 的，由于 O(m) 与 O(n^2) 同级，总时间复杂度是 O(n^3) 的，而目前已有的题解是 O(n^2m) 也就是 O(n^4) 的，所以这个做法可以很轻松卡过。

关于正确性，我有一个很长的证明，但考虑到这个构造比较自然，而且证明太过麻烦，所以不放了，我希望看到一个简洁的证明或者证伪，不过，即使你 hack 掉了我次大值最多两个的情况，我再多枚举一个次大值的个数只会使时间复杂度多带一个 \ln n，依然是严格优于正解的，同时，这里面有很多优化比如如果找到最大值比较多的就停，常数极小，大部分情况下我可以直接去掉一个 O(n)，而且 m 一般是远小于 n^2 的，可以证明，由于数据过小，一定造不出来能 hack 掉我不同个数不超过 3 个这条性质，经过实测，n 开到 10^3 也很难造这样的数据，反正我随了近 10^3 组数据没随出来，自己造了一些特殊数据都过了。

说句闲话，如果你不判次大值有两个可以拿到 91 pts。

截至到现在：

最优解时间 102 ms，空间 680 kb。

正解最优时间 116 ms，空间 684 kb。

#include <bits/stdc++.h>
#define il inline
#define rg register
#define cit const rg unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("1.in","r",stdin),freopen("1.out","w",stdout)
#define int rg unsigned
#define void il void
#define ll long long
#define ull unsigned ll
#define vector basic_string
#define vint vector<unsigned>
#define sca(a) for(int $=0;$<n;cin>>a[++$])using namespace std;constexpr unsigned N=30+1;
unsigned n,m,a[N],id[N],ans[N],b[N];
void init(){sca(a);
    for(int i=1;i<=n;++i)id[i]=i;
    for(int i=1;i<=n;++i)
        for(int j=1;j<n;++j)
            if(a[id[j+1]]>a[id[j]])swap(id[j],id[j+1]);
}
void solve(){cin>>n>>m;m-=n;init();
    if(m%n==0){cout<<"0\n";
        for(int i=1;i<=n;++i)cout<<m/n+1<<' ';
        return;
    }if(m%(n-1)<=m/(n-1)){
        ans[id[n]]=m%(n-1);int cnt=0;
        for(int i=1;i<n;++i)ans[id[i]]=m/(n-1);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(ans[j]>ans[i])cnt+=a[i];
        cout<<cnt<<'\n';for(int i=1;i<=n;++i)cout<<ans[i]+1<<' ';
        return;
    }if(n==2){cout<<a[id[1]]<<'\n';
        ans[id[1]]=m,ans[id[2]]=0;
        cout<<ans[1]<<' '<<ans[2];return;
    }int ll cnt=0;
    for(int l=n-2,r=n;l;--l,--r){
        for(int i=0;i<m;++i){
            cit t=m-i,tl=t/l,tr=(t-tl*l)/(n-r+1);
            if(((tl*l+i+tr*(n-r+1))^m)||i<tr||i>tl)continue;
            ans[id[l+1]]=i;
            for(int j=1;j<=l;++j)ans[id[j]]=tl;
            for(int j=n;j>=r;--j)ans[id[j]]=tr;
            for(int j=l+1;j<=n;++j){
                if(ans[id[l]]>ans[id[j]])cnt+=a[id[j]]*l;
                if(ans[id[l+1]]>ans[id[j]])cnt+=a[id[j]];
            }l=1;break;
        }
    }for(int l=n-3,r=n;l;--l,--r){
        for(int i=0;i+i<m;++i){
            cit t=m-i-i,tl=t/l,tr=(t-tl*l)/(n-r+1);
            if(((tl*l+i+i+tr*(n-r+1))^m)||i<tr||i>tl)continue;
            b[id[l+1]]=i;b[id[l+2]]=i;
            for(int j=1;j<=l;++j)b[id[j]]=tl;
            for(int j=n;j>=r;--j)b[id[j]]=tr;int ll _=0;
            for(int j=l+1;j<=n;++j){
                if(b[id[l]]>b[id[j]])_+=a[id[j]]*l;
                if(b[id[l+1]]>b[id[j]])_+=a[id[j]]<<1;
            }if(_<cnt){cnt=_;memcpy(ans,b,sizeof b);}
            else continue;l=1;break;
        }
    }cout<<cnt<<'\n';for(int j=1;j<=n;++j)cout<<ans[j]+1<<' ';  
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}

为过审，删除了部分用不到的宏定义，不保证没有不小心多删