专栏文章

题解：P11577 [CCC2020] Epidemiology

zzyxjeek
P11577题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqh7v6y
此快照首次捕获于
2025/12/04 04:45
3 个月前
此快照最后确认于
2025/12/04 04:45
3 个月前
查看原文

1.题目描述

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

2.思路

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

3.注意事项

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

4.代码

C
#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.时间复杂度

循环变量 dd 在每次循环中都会乘上 RR，所以时间复杂度是 O(log⁡RP)\mathcal O(\log_R P)。
The End

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...