脚本宝典收集整理的这篇文章主要介绍了cf1491 C. Pekora and Trampoline（思维），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题意：

n 个蹦床，每个蹦床有强度 a[i]。从第 i 个蹦床起跳会跳到第 i+a[i] 个蹦床处，然后 a[i] 会 -1，但不能小于1。每轮任选一个蹦床开始跳，跳到超过 n 出界为止。问把所有 a[i] 变成1至少要多少轮。n<=5000，时间限制 2s

思路：

数据范围太小，直接 (O(n^2)) 模拟。

贪心地跳，每轮从第一个大于1的 a[i] 起跳，跳 a[i]-1 轮直到 a[i] 变成1为止。在这个过程中，a[i] 减为1，a[i+2], a[i+3], ..., a[i+a[i]] 都可以减1。用b[i] 记录前面的位置对位置 i 的贡献。

如果 i 之前的位置对 i 的贡献 b[i] < a[i] - 1，那么 a[i] 只靠之前的贡献不能变为1，还要另外从 i 处起跳 a[i]-1-b[i] 轮。

如果 i 之前的位置对 i 的贡献 b[i] == a[i] - 1，那么 a[i] 靠之前的贡献刚好变为1。

如果 i 之前的位置对 i 的贡献 b[i] > a[i] - 1，那么 a[i] 靠之前的贡献变为1后，还会把多出来的 b[i]-a[i]+1 点贡献传递给后面的位置。因为此时 a[i]==1，所以只能传给下一个位置 i+1 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5005;
int a[N], b[N];
signed main()
{
    int T; cin >> T; while(T--)
    {
        int n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        fill(b+1, b+n+1, 0);

        for(int i = 1; i <= n; i++) if(a[i] > 1)
            for(int j = i + 2; j <= min(i + a[i], n); j++)
                b[j]++; //每个a[i]对后面的贡献

        for(int i = 1; i <= n; i++)
            if(b[i] > a[i] - 1) b[i+1] += b[i] - a[i] + 1;

        ll ans = 0;
        for(int i = 1; i <= n; i++)
            if(a[i] - 1 > b[i]) ans += a[i] - 1 - b[i];
        cout << ans << 'n';
    }

    return 0;
}

可以差分优化：

for(int i = 1; i <= n; i++) if(a[i] > 1)
{
    int l = i + 2, r = min(i + a[i], n);
    if(l <= r) ++b[l], --b[r+1];
}
for(int i = 1; i <= n; i++) b[i] += b[i-1]; //变回原数组

脚本宝典总结

以上是脚本宝典为你收集整理的cf1491 C. Pekora and Trampoline（思维）全部内容，希望文章能够帮你解决cf1491 C. Pekora and Trampoline（思维）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。