题意分析

题目描述 Kicc 需要移山，但移动石头会产生噪音，吸引野生动物。动物在听到噪音时会向山移动，否则会返回起始点。一旦动物到达山的位置，Kicc 会被吃掉。Kicc 每天有 t 单位时间，每单位时间能处理 x 单位石头。有 m 只动物，每只动物起始距离山 d_i，速度为 s_i（单位时间移动距离）。目标是最大化 Kicc 每日处理的石头量，同时避免被动物吃掉。

关键约束：

• 动物行为：听到噪音时向山移动，否则沿原路返回起始点。
• Kicc 安全：若动物在移动后距离 ≤ 0，则到达山，Kicc 被吃。
• 时间单位：仅整数单位，Kicc 可工作或休息。
• 优化目标：在安全前提下，最大化处理石头量 总工作量 = 工作时间 × x。

解题思路

核心策略：安全时间窗口

1. 安全时间 d 计算：

   • 每只动物到达山的最小时问单位为 k_i = ceil(d_i / s_i)。
   • 由于动物到达时 Kicc 会被吃，因此他必须在 k_i - 1 单位时间内停止工作。
   • 对所有动物取最小安全时间：
     d = min_i ( (d_i - 1) // s_i )
     这里 // 表示整数除法（向下取整），因为动物在第 k_i 时间到达，Kicc 最多工作到 k_i - 1 时间。

2. 工作量计算：

   • 无动物 (m = 0)：Kicc 可全程工作，总工作量 = t × x。
   • 有动物：
     • 若 t ≤ d：全程安全，总工作量 = t × x。
     • 若 t > d：仅安全时间 d 内可工作，总工作量 = d × x。

算法正确性证明

• 安全时间 d 的合理性：
  d = min_i ( (d_i - 1) // s_i ) 确保所有动物在 d 时间内移动距离小于 d_i（即未到达山）。
  例如：动物 d_i = 100, s_i = 1 时，d = (100 - 1) // 1 = 99，动物在时间 99 移动 99 单位，距离山 1 单位，未到达。
• t > d 时不可继续工作：
  若在 d 时间后工作，动物会继续移动。例如动物在 d 时间后距离山为 p_i = d_i - d * s_i ≥ 1，但若工作，动物移动 s_i 后距离为 p_i - s_i，可能 ≤ 0（如 p_i = 1, s_i = 1 时距离为 0，动物到达山）。因此 d 时间后工作不安全。

复杂度分析

• 时间复杂度：O(m)，遍历每只动物计算 d。
• 空间复杂度：O(1)，仅存储变量。

代码实现

#include <iostream>
#include <climits>
using namespace std;
#define INT_MAX 1e9
int main() {
    int t, x, m;
    cin >> t >> x >> m;

    // 无动物时全程工作
    if (m == 0) {
        cout << t * x;
        return 0;
    }

    int d = INT_MAX;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        // 计算安全时间 d = min((d_i - 1) // s_i)
        int k = (a - 1) / b; // 整数除法
        if (k < d) d = k;
    }

    // 处理 d 为负情况
    if (d < 0) d = 0;

    // 输出最大工作量
    if (t <= d) cout << t * x;
    else cout << d * x;
    return 0;
}