AT_abc365_c 题解

· · 题解

题目传送门

思路

题目要求补贴限额 x 的最大可能值是多少，可以发现其答案具有单调性，考虑使用二分答案。

对于每一次选择的 x，对于第 i 个人选择 \min(x,A_i)，判断其和是否 >M。若 \displaystyle\sum_{i=1}^{N}A_i<M，那么如果补贴限额可以无限大。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
long long read(){long long x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e5+10,MAX=1e9;
int n,a[N];
long long m;
bool check(int x){
    long long sum=0;
    for(int i=1;i<=n;++i){
        sum+=min(x,a[i]);
        if(sum>m)
            return false;
    }
    return true;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    int l=0,r=MAX;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid+1;
        else r=mid-1;
    }
    if(r!=MAX)
        printf("%d\n",r);
    else printf("infinite\n");
    return 0;
}