P7585 [COCI2012-2013#1] LJUBOMORA 题解

SunsetSamsara · 2021-05-26 07:32:41 · 题解

这题从条件相同的颜色与分给一个孩子最多的弹珠数量可以看出可以用二分完成该题.

既然是二分,就有 2 个中点:判定函数与边界条件.判定函数可以说是十分经典的了,下面直接贴代码:

bool judge(int x){
    int sum=0;
    for(int i=1;i<=M;++i)
        sum+=(A[i]+x-1)/x;
    //只要有余数就得+1,相当于(A[i]+x-1)/x
    return sum<=N;
}

边界条件中,我采用了典型(也不容易错)的判定方式:左闭右开区间.

int left=0,right=0x3f3f3f3f;
while(left+1<right){
    int mid=(left+right)>>1;
    if(judge(mid))right=mid;
    else left=mid;
}
printf("%d\n",right);

所以,最后贴完整代码:

#include<stdio.h>
int N,M,A[300001];
bool judge(int x){
    int sum=0;
    for(int i=1;i<=M;++i){
        if(A[i]%x)++sum;
        sum+=A[i]/x;
    }
    return sum<=N;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)scanf("%d",A+i);
    int left=0,right=0x3f3f3f3f;
    while(left+1<right){
        int mid=(left+right)>>1;
        if(judge(mid))right=mid;
        else left=mid;
    }
    printf("%d\n",right);
    return 0;
}