本文共 1382 字，大约阅读时间需要 4 分钟。

要解决这个问题，我们需要找到将所有蹦床的弹力值减少到1所需的最少跳跃次数。以下是详细的解决步骤：

解题思路

代码实现

#include 
   
    
using namespace std;
typedef long long ll;
#define ENDL "\n"
const int maxn = 5e3 + 10;
int a[maxn];
ll cnt[maxn];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            a[i] = 0;
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            cnt[i] += cnt[i - 1];
            int res = 0;
            if (i + a[i] > n) {
                res += i + a[i] - n;
                a[i] = n - i;
            }
            res += a[i] - 1;
            if (cnt[i] > res) {
                cnt[i + 1] += cnt[i] - res;
                cnt[i + 2] -= cnt[i] - res;
                cnt[i + 2]++;
                cnt[i + a[i] + 1]--;
            }
            ans += max(0LL, res - cnt[i]);
        }
        cout << ans << ENDL;
    }
    return 0;
}
   

代码解释

这种方法通过差分数组高效地维护了每个跳跃对后续点的影响，确保了算法的高效性和正确性。

转载地址：http://fvqq.baihongyu.com/