CodeForces - 748E Santa Claus and Tangerines（枚举）

思路：求使得分得的最小值最大。由于最大值为1e7，所以可以直接从大到小枚举最小数i。当分得的个数总和大于人数时，代表此即为最小值（从大到小枚举，也即为最小值最大）。则a[i/2]=a[i/2]+a[i];a[(i+1)/2]=a[(i+1)/2]+a[i]（a[i]代表可以由i分得的数的个数，初值为1）。tot记录当前值i时已分得的不小于i的数的个数，每次判断前需要减去i上一状态的个数（因为已将其分为两个数），则tot不小于人数时退出。注意i==1时i*2-1的判断。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxn=1e7+50;const int INF=0x3f3f3f3f;int n,num;LL a[maxn];int main(){    LL tot=0;    int maxx=-INF;    memset(a,0,sizeof(a));    scanf("%d%d",&n,&num);    for(int i=1; i<=n; i++)    {        int x;        scanf("%d",&x);        a[x]++,tot+=x;        maxx=max(maxx,x);    }    if(tot<num) printf("-1/n");    else    {        tot=0;        for(int i=maxx; i>0; i--)        {            tot+=a[i];            if(i*2<=maxx) tot-=a[i*2];            if(i*2-1<=maxx&&(i!=1)) tot-=a[i*2-1];            if(tot>=num)            {                printf("%d/n",i);                break;            }            a[i/2]+=a[i];            a[(i+1)/2]+=a[i];        }    }    return 0;}