上传RAM 题解

一、题目回顾

需要上传 $n$ GB 的 RAM。每秒可以上传 $0$ 或 $1$ GB。但在任意连续的 $k$ 秒内，最多只能上传总共 $1$ GB。求上传 $n$ GB 所需的最短秒数。

数据范围：$t$ 组测试，$1 \le t \le 10^4$，$1 \le n, k \le 100$。

二、思路分析

关键约束

任意连续 $k$ 秒内，最多上传 $1$ GB。 这意味着：

• 当你上传 $1$ GB 后，接下来的 $k-1$ 秒内不能再上传任何数据（否则会违反窗口限制）。
• 因此相邻两次上传之间必须至少间隔 $k-1$ 秒。

上传时间表

按照最紧凑的方式安排上传：

因此最短总秒数为：

验证样例

• $n=5, k=1$：$1 + 4 \times 1 = 5$ ✓
• $n=2, k=2$：$1 + 1 \times 2 = 3$ ✓
• $n=2, k=3$：$1 + 1 \times 3 = 4$ ✓
• $n=1, k=7$：$1 + 0 \times 7 = 1$ ✓
• $n=11, k=5$：$1 + 10 \times 5 = 51$ ✓
• $n=100, k=100$：$1 + 99 \times 100 = 9901$ ✓

三、复杂度

每组 $O(1)$ 计算，总复杂度 $O(t)$。

四、AC 代码

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

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