本文共 1382 字,大约阅读时间需要 4 分钟。
要解决这个问题,我们需要找到将所有蹦床的弹力值减少到1所需的最少跳跃次数。以下是详细的解决步骤:
#includeusing 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;}
cnt来记录每个点的贡献。res,并更新差分数组。ans中。这种方法通过差分数组高效地维护了每个跳跃对后续点的影响,确保了算法的高效性和正确性。
转载地址:http://fvqq.baihongyu.com/