题解 | 汉堡猪猪分糖果

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dbg(x) cout<<#x<<": "<<(x)<<endl;
//n个糖果，m个同学，尝试每人分配cnt个，能否成功分配
int check(int n,int m,int cnt){
    if(!m)return true;
    int rest=n-m*cnt;
    for(int i=62;i>=0;i--){
        if(cnt&(1ll<<i))continue;
        if(rest>=(1ll<<i)){
            rest=max(rest%(1ll<<i),rest-(1ll<<i)*m);
        }
    }
    if(rest)return false;
    return true;
}
signed main() {
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        int ans=0;
        for(int i=n/m;i>=0;i--){
            if(check(n,m,i)){
                ans=i;
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

最优分配 与运算的结果设为 x ， 那么所有 a[i] 都一定是x的二进制位的超集，那么所有值都应该大于x，直觉来看a[i] 都分配 n/m 就是最优结果，但实际上 这么分配后余下的糖果数量为 rest = n % m, rest还要接着分配给m个同学，有可能会使得已分配的 x 的二进制位产生进位，使得一部分同学分配的值不再包含 x ，所以 n/m 不一定能够成功分配，但最优结果 x <= n/m ,同时直觉告诉我们答案就在 n/m 附近，所以直接从 n/m 向下枚举，然后判断每一种分配是否能够成功完成；

判断的逻辑： 对于当前分配判断值 cnt ， 我们已经分配了 m 个 cnt， 我们要将剩余值rest 分配给所有人，同时不占用已经分配的二进制位，所以，直接从最高位进行枚举， 如果 cnt & (1ll<<i) ==0 ，我们就可以占用这一位，就贪心的将糖果分配在这一位上，如果最终 cnt =0，说明可以成功分配；