问题描述
给定数组 a[1..n]，每次操作可以选择一个下标 i，将 a[i] 增加 i。最多进行 k 次操作，求能达到的最小值的最大值 x（使得所有 a[i] >= x）。
核心思路
二分答案 + 贪心验证
- 最小值最大 → 二分答案
- 验证函数：计算达到目标值
mid需要多少次操作
算法图解
图1: 操作示意
每次操作:
a[1]: +1, +1, +1, ... (每次+1)
a[2]: +2, +2, +2, ... (每次+2)
a[3]: +3, +3, +3, ... (每次+3)
...
a[i]: +i, +i, +i, ...验证公式:
sum = Σ ceil((mid - a[i]) / i)= Σ (mid - a[i] + i - 1) / i
图2: 二分过程
L = 1, R = 2e18mid = (L + R + 1) / 2↓
验证 mid:sum > k → R = mid - 1sum ≤ k → L = mid↓
直到 L == R
为什么 R = 2e18
1. long long 上限: 9.22 × 10^18
2. R = 2 × 10^18 < 9 × 10^18 → 不会溢出 long long
3. 操作次数 k: 题目保证在安全范围内
4. 每次操作最大增量: i ≤ 2 × 10^5
5. 理论最大可达值: a[i] + k × i ≈ 10^23 (超出范围)
6. 但 2e18 是题目的合理上界，保证答案安全
代码注释
#include <bits/stdc++.h>
#define LL long long
using namespace std;int n;
LL k, a[200005];int main() {cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];LL L = 1, R = 2e18; // 二分范围// 最小值最大 → 单调性: 值越大，需要的操作数越多while (L < R) {LL mid = (L + R + 1) / 2; // 上取整，避免死循环// 计算达到 mid 需要多少次操作LL sum = 0;for (int i = 1; i <= n; i++) {if (a[i] >= mid) continue; // 已经满足// 需要 (mid - a[i] + i - 1) / i 次操作// 向上取整: (x + y - 1) / ysum += (mid - a[i] + i - 1) / i;if (sum > k) break; // 提前剪枝}// 操作数足够 → mid 可行，尝试更大if (sum <= k) L = mid;else R = mid - 1; // mid 太大}cout << L << endl;return 0;
}
关键公式
第 i 个元素需要 t 次操作:
a[i] + t × i ≥ mid
t ≥ (mid - a[i]) / i
t = ceil((mid - a[i]) / i) = (mid - a[i] + i - 1) / i总操作数:
sum = Σ t (对所有 a[i] < mid 的 i)
复杂度分析
| 复杂度 | 值 |
|---|---|
| 时间 | O(n × log R) |
| 空间 | O(n) |
典型示例
输入:
n = 3, k = 4
a = [1, 5, 10]验证 mid = 6:
- a[1] = 1 < 6: (6-1+0)/1 = 5 次
- a[2] = 5 < 6: (6-5+1)/2 = 1 次
- sum = 6 > k = 4, 不可行验证 mid = 4:
- a[1] = 1 < 4: (4-1+0)/1 = 3 次
- a[2] = 5 ≥ 4: 跳过
- sum = 3 ≤ k, 可行答案: 4
核心思想
本质是二分答案的经典应用:
1. 最小值的最大值 → 具有单调性
2. 验证 mid 需要多少操作 → 贪心计算
3. sum ≤ k → mid 可行，L = mid
4. sum > k → mid 太大，R = mid - 1