题解：P11577 [CCC2020] Epidemiology

zyxjeek · 2025-01-18 09:14:56 · 题解

1.题目描述

有 N 个人在第 0 天患病。当一个人患病时，他会在明天感染 R 个人，随后便不再感染他人。没有一个人会被感染超过一次。我们想要确定造成 P+1 个人患病的最早时间。

2.思路

简单模拟即可。我们用变量 d_i 记录第 i 新增的患病人数，由于每人能感染 R 人，所以 d_i = d_{i-1} \times R。不断让 N 加上 d_i，直到 N > P。此时的天数 i 就是答案。

3.注意事项

• 退出循环时，i 的值是感染 P 个人后的第二天。所以答案是 i-1。

4.代码

#include <bits/stdc++.h>
using namespace std;

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

    int p, n, r;
    cin >> p >> n >> r;
    int d = n, i;
    for (i = 1; n <= p; i++) {
        d *= r;
        n += d;
    }
    cout << i-1 << endl;
    return 0;
}

5.时间复杂度

循环变量 d 在每次循环中都会乘上 R，所以时间复杂度是 \mathcal O(\log_R P)。

The End