练35.1 传输数据

解题思路

最初1台持有数据，每秒每台最多再传k台，所以持有量最多乘k+1。循环扩张直到达到n，次数即最短时间。

正确性说明

t秒后持有量不超过(k+1)^t；每秒向尚未持有的不同电脑传输能达到该上界或覆盖剩余全部，因此首次达到n的t既是下界又可实现。

易错点

n=1为0秒；累计用long long并可截为n。

复杂度

时间O(log_(k+1)n)，空间O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k;
    cin >> n >> k;
    long long have = 1;
    int t = 0;
    while (have < n) {
        have = min(n, have * (k + 1));
        t++;
    }
    cout << t << "\n";
    return 0;
}