CodeForces 748E. Santa Claus and Tangerines(二分，递推)

每个数可以分成两个新的数 i/ 2 、(i+1)/2 分后的数可以继续分，但不允许分1=1+0

最后分给每个人，求分得的数最小的人分得的数最大能多少。

有两个方法。

第一个方法是二分答案，然后从1e7到二分的值按照i的奇偶性把i的值传给i/2或i/2和

i/2+1，然后计算当前二分的值是否能分给m个人。时间复杂度是n*logn*logn，勉强能过.

参考博客：点击打开链接

第二个方法是倒着直接枚举答案，枚举到i时，把当前值传给i/2和(i+1)/2两个儿子，统计

当前值能分给多少人时需要减去父亲的贡献，i的父亲有i*2-1, i*2, i*2+1, 但是为防止重复

删去父亲贡献，每次只需减去i*2-1, i*2这两个父亲（如只有一个7片的橘子，分成3 4，

枚举到4时删除7 8，到3时删除5 6，不用再删除7）。复杂度是n，快了很多。

参考博客：点击打开链接

二分代码：

#include<bits/stdc++.h>  using namespace std;typedef long long ll;const int maxn = 1e6+5;const int maxm = 1e7+5;ll a[maxn], num[maxm], n, k;bool judge(ll x){    ll cnt = 0;    memset(num, 0, sizeof(num));    for(int i = 1; i <= n; i++)        num[a[i]]++;    for(int i = maxm-1; i >= x; i--)    {        if(i/2 >= x)        {            if(i&1)            {                num[i/2] += num[i];                num[i/2+1] += num[i];            }            else num[i/2] += num[i]*2;        }        else cnt += num[i];    }    return cnt >= k;}int main(void){    while(cin >> n >> k)    {        ll l = 0, r = 1e7;        for(int i = 1; i <= n; i++)            scanf("%I64d", &a[i]);        int ans = -1;        while(l <= r)        {            ll mid = (l+r)/2;            if(judge(mid)) l = mid+1, ans = mid;            else r = mid-1;        }        PRintf("%d/n", ans);    }    return 0;}
方法二：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e6+5;ll n, k, mx, cnt, a[maxn], num[maxn*10];int main(void){    while(cin >> n >> k)    {        mx = cnt = 0;        memset(num, 0, sizeof(num));        for(int i = 1; i <= n; i++)        {            scanf("%I64d", &a[i]);            cnt += a[i];            num[a[i]]++;            mx = max(mx, a[i]);        }        if(cnt < k) puts("-1");        else        {            cnt = 0;            for(int i = mx; i; i--)            {                cnt += num[i];                if(i*2 <= mx) cnt -= num[i*2];                if(i*2-1 <= mx && i != 1) cnt -= num[i*2-1];                if(i*2+1 <= mx)                if(cnt >= k) { printf("%d/n", i); break; }                num[i/2] += num[i];                num[(i+1)/2] += num[i];            }        }    }    return 0;}