机器人宿管指南

GitHub跳转原题关系图Canvas 关系图返回列表

模拟固定天数的苹果消耗过程，并对机器人数量二分答案。

OJ: shumeng

题目 ID: CSP202605B

难度:未知

标签:二分答案模拟单调性

日期: 2026-07-31 16:22

目录

  1. 形式化题目
  2. 思路
    1. 固定机器人数量后直接模拟
    2. 单调性二分
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

初始有 nn 个苹果。从第 11 天起，每天先丢弃 ⌈t⋅k/100⌉\lceil t\cdot k/100\rceil 个变质苹果（tt 为当天开始时剩余的苹果数），然后每个机器人吃一个苹果。求最多能入住多少个机器人，使得第 mm 天每个机器人吃到一个苹果后剩余苹果数不小于 00。

思路

固定机器人数量后直接模拟

若机器人数量为 xx，每天的过程是确定的：先丢弃变质苹果，再检查剩余苹果是否够 xx 个机器人吃，不够就失败。用 (t * k + 99) / 100 整数计算向上取整即可，全程只用整数，避免浮点误差。

单调性二分

机器人越多，每天消耗越大，越难支撑到第 mm 天，因此“是否可行”关于 xx 单调。对 [0,n][0,n] 做二分，can_feed(mid) 可行就向右半段搜索，否则向左半段，最终得到最大的可行值。注意 nn 可达 101810^{18}，全部使用 long long。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

long long apples_initial; // 初始苹果数量 n
long long spoil_percent;  // 每日变质比例 k%
long long days;           // 需要支撑的天数 m

// 判断 robots 个机器人能否支撑 days 天：
// 每天先丢弃 ceil(t*k/100) 个变质苹果，再让每个机器人吃一个。
bool can_feed(long long robots) {
    long long apples = apples_initial;
    for (long long day = 0; day < days; day++) {
        long long spoiled = (apples * spoil_percent + 99) / 100; // 向上取整
        apples -= spoiled;
        if (apples < robots) return false; // 不够吃就失败
        apples -= robots;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> apples_initial >> spoil_percent >> days;

    // 机器人越多越难支撑，可行性单调，二分最大的可行值。
    long long left = 0, right = apples_initial;
    while (left < right) {
        long long middle = left + (right - left + 1) / 2;
        if (can_feed(middle)) {
            left = middle;
        } else {
            right = middle - 1;
        }
    }
    cout << left << '\n';
    return 0;
}

复杂度

  • 时间：二分约 log⁡n\log n 次，每次检查模拟 mm 天，总时间复杂度 O(mlog⁡n)O(m\log n)。
  • 空间：只使用常数个变量，空间复杂度 O(1)O(1)。

总结

把每天的过程封装成可行性检查后，资源数量问题就变成了标准的单调性二分。关键是向上取整要用整数运算处理，避免 double 丢失精度。