AT_abc365_c

AnnaQ · 2024-08-08 20:04:39 · 题解

思路

一道非常基础的二分题，但是当时我足足吃了6发罚时，因为我一开始没有想到要用二分。

在考场上写过这道题的暴力做法的同学们应该大概就清楚了二分是优化的那部分得了，没写过的同学继续往下看，写过了的可以直接去看代码了。

二分的检查函数完全就是根据题意而写的，这部分我在此就不细讲了，看不懂的同学建议多读几遍题。

二分主要是优化了找 x 的值的这步，这样这步从原来的从 M / N 一直找直到找到不满足条件了才结束，然后输出找到的数减一这么高的复杂度优化到了 O(log10^9) ，简直不要快太多，由于题目要求最大，所以找到符合的之后 l 要变大（下次的 mid 变大），不符合才是 r 变小（下次的 mid 变小）。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200010],l,r = 1e9,ans,sum;
bool check(int x)//根据题意而写的check函数
{
    int sum = 0;
    for(int i = 1;i <= n;i++) sum += min(x,a[i]);
    return sum <= m;
}
signed main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i],sum += a[i];
    if(sum <= m)//如果所有人所需要的补贴都加在一起都没超过m，那x就可以无限大了
    {
        cout << "infinite" << endl;
        return 0;
    }
    while(l <= r)//二分模版
    {
        int mid = (l + r) / 2;
        if(check(mid))
        {
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}