大家好，今天我们来看CSP202605B. 机器人宿管指南这道题目

首先，我们想这样一个问题：假设现在有x个机器人（x已经给定），根据题目中给出的变质规律，通过模拟，我们可以判断出这些苹果能否撑过m天，这个过程的时间复杂度为O（m）

而根据题意，我们不难看出：机器人数量越多，苹果能撑过的时间就越短。这是一个单调的函数规律

单调性意味着答案可以通过二分查找来获得。

由于题目保证答案不超过 10⁹，我们将二分区间初始化为 left = 0，right = 10⁹，每次取中点 mid = (left + right) / 2，并调用 check(mid) 判断 mid 个机器人能否撑过 m 天：

• 若 check(mid) 为真，说明 mid 是一个可行解，答案至少为 mid，因此尝试更大的值，令 left = mid + 1；

• 若 check(mid) 为假，说明机器人太多了，需要减少，令 right = mid - 1。

重复上述过程直到 left > right，此时 ans 中存储的就是最大的可行机器人数量。

代码如下：

 # include <bits/stdc++.h>

using namespace std;

#define itn int
#define ll long long
#define ld long double
#define mod 998244353

ll n,k,m;
bool check(ll x) {                            // 对有x个机器人的情况进行判断
    ll cur = n;
    for (int i = 0 ; i < m ; i ++) {          // 遍历m天
        ll bad = (cur * k + 99) / 100;
        if (bad > cur) bad = cur;
        cur = cur - bad - x;
        if (cur < 0) return false;            // 不够m天
    }
    return true;                              // 够m天
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k >> m;
    ll left = 0;
    ll right = 1e9;
    ll ans = 1;
    /*                           二分                          */
    while (left <= right) {              
        ll mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

感谢阅读，欢迎在评论区留言讨论

转载请注明出处