Codeforces Global Round 13 C. Pekora and Trampoline 贪心

传送门：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();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/01/codeforces-global-round-13-c/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！