传送门：https://codeforces.ml/contest/1491/problem/C
题意
给一个数组a，可以从任意地方开始跳。假如在第i个开始跳，那么跳到下一个的位置是I+a[i]，并且当前位置a[i]–，跳到超过n为止，这算一个操作数。问，当操作数为多少时，可以使数组全部变成1，求出最少的操作数。
思路
比赛的时候知道是贪心，但是不会贪，只能暴力模拟$n^3$，n虽然只有5000，但也会T。 而贪心的话是$n^2$，复杂度是够的。
考虑每一次都从第一个走，这无所谓，如果前面全是1，那么会直到第一个不为1的位置开始跳。
所以从前往后遍历，考虑当前第i位，有多少是要我们操作的，有多少是从之前的操作跳过来的 所以这些不对答案做贡献。
假设第i个，那么他会跳到[i+2,i+a[i]]，这些个位置都可以通过i跳到， 而第i+1个位置是必然跳到的，并且第i个位置可以从之前操作中跳过来，那么第i+1位置也是可以从之前操作跳过来。
所以需要一个数组b来记录，第i个位置有多少是从前面位置跳过来的，这些不对答案做贡献。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void solve() {
int _;
cin >> _;
while (_--) {
int n;
cin >> n;
ll a[n + 10], b[n + 10];
for(int i = 1;i <= n; i++) cin >> a[i];
mem(b, 0);
ll ans = 0;
for(int i = 1;i <= n; i++) {
ll temp = b[i];
if(a[i] > temp + 1) {
ans += a[i] - temp - 1;
temp += a[i] - temp - 1;
}
b[i + 1] += temp - a[i] + 1;
if(i + 2 <= n) for(int j = i + 2;j <= min(1ll* n, i + a[i]); j++) b[j]++;
}
cout << ans << endl;
}
}
signed main() {
solve();
}
|