资讯详情

atc abc459F

题意

给定长度为 \(n\) 非负整数序列 \(a\)，每次操作可以使 \(a_i := a_i-1\)，\(a_{i+1}:=a_{i+1}+1\)，求让 \(a\) 严格递增的最少操作次数.

\(2\le n\le 6\times 10^5\).

思路

首先，让 \(a_i:=a_i-i\)，将严格递增的约束转化成不减，同时全部加上 \(n\) 保证调整后非负.

显然，调整某个严格递减块的最优策略是让整块尽可能平均，于是可以使用 PAVA 算法，记两块分别为 \((sum_1,len_1)\)，\((sum_2,len_2)\)，合并条件是：

\[\left\lceil\frac{sum_1}{len_1}\right\rceil \gt \left\lfloor\frac{sum_2}{len_2}\right\rfloor \]

考虑最后如何计算操作次数.

记 PAVA 算法构造出的数组为 \(b\)，让 \(a_i:=a_i+i-n\)，\(b_i:=b_i+i-n\).

观察一次操作的影响，发现是让 \(pre_i:=pre_i-1\)，\(pre\) 是数组的前缀和，于是将 \(a,b\) 求前缀和后逐项相减即可.

时间复杂度 \(\mathcal{O}(n)\).

代码

//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;cin >> n;vector<ll> a(n+1);for (int i=1;i<=n;i++){cin >> a[i];a[i] = a[i]-i+n;}stack<pair<ll,ll>> stk;for (int i=1;i<=n;i++){pair<ll,ll> cur = {a[i],1};while (!stk.empty()){auto top = stk.top();if ((top.first+top.second-1)/top.second>cur.first/cur.second){cur.first += top.first;cur.second += top.second;stk.pop();} else break;}  stk.push(cur);    }vector<ll> b{0};while (!stk.empty()){auto [sum,len] = stk.top();stk.pop();ll p = sum/len;ll r = sum%len;for (int i=0;i<r;i++){b.push_back(p+1);}for (int i=0;i<len-r;i++){b.push_back(p);}}reverse(b.begin()+1,b.end());for (int i=1;i<=n;i++){a[i] += i-n+a[i-1];b[i] += i-n+b[i-1];}ll res = 0;for (int i=1;i<n;i++){res += a[i]-b[i];}cout << res << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}