题解 | #小红的数组操作#

~~没打，但是在群里看到有人求助F，过来切掉后发现没人写相关题解于是怒水一篇~~

【题意】

给定序列 $a_n$ , 每次可以将某对相邻的数 $(a_i,a_{i 1})$ 变为 $(a_i-1,a_{i 1} 1)$ , 求最小操作次数使得序列变为升序并求操作后的序列。

【题解】

首先考虑把严格升序转化为更灵活的单调不减，根据相关经验可以直接进行 $a_i \leftarrow a_i-i$ 赋值，这样就把升序丢掉了(因为作差之后若 $a'_i \le a'_j(i < j)$ , 必有 $a_i = a'_i i< a'_j j = a_j$ )。

然后考虑接下来的情况怎么处理。

然后可以发现，对于序列的操作是具有贪心性质的，即 $a_1 \sim a_{i 1}$ 的最优解是在 $a_1\sim a_i$ 的最优解的基础上得到的。此外，为了使得操作数尽可能少，开始转移值的位置也必须尽可能靠近 $i$ 。

于是我们发现，单次向外拓展 $a_i$ 的操作的具体流程如下:

首先找到最大的 $l(1\le l\le i)$ , 使得 $\frac{\sum_{j=i}^{l} a_j}{i-l 1} \ge a_{l-1}$ 。换句话说，就是找到能够保证将 $l \sim i$ 全部维护成这一段的平均值之后还能保证整个序列单调不减性质的最大的一个左端点，然后开始转移。
转移过程十分简单，将这一段直接推成连续的平均值与平均值+1即可。如果 $a_i$ 最大，那么 $l=i$ , 无需维护; 反之它就小于前面某些值，为了保持序列性质，它必须最大，那么这个最优的最大就是平均值，一方面它自己操作次数最少，另一方面后续操作中它需要递给后续数字的值也是最小的。

时间瓶颈在找这个 $l$ 上，但实际上我们可以直接挂个单调栈同时维护值和出现次数。

同时有些操作面对负数会出现细节问题，因此我们可以减掉最小值来保证序列非负，从而避免此问题。

具体操作显然，元素数量 $O(n)$ , 每个元素最多入栈出栈一次，时间复杂度 $O(n)$ 。

得到答案序列后计算操作数的方式同样显然，从头推到尾即可。

核心代码

int n;
i64 mn(1ll*INF*INF),a[MAXN];
i64 ans[MAXN];
void solve()
{
    cin >> n; vector<pli> st;
    For(i,1,n) cin >> a[i], a[i] -= i, chkmin(mn,a[i]);
    For(i,1,n)
    {
        i64 sum(a[i]-=mn); int cnt(1);
        while((!st.empty()) && sum/cnt < st.back().first)
        {
            auto [x,t] = st.back(); st.pop_back();
            sum += x*t; cnt += t;
        }
        st.emplace_back(sum/cnt,cnt-sum%cnt);
        if(sum%cnt) st.emplace_back(sum/cnt+1,sum%cnt);
    }
    int pos(0);
    For(i,1,n)
    {
        if(!st[pos].second) ++pos;
        --st[pos].second, ans[i] = st[pos].first;
    }
    i64 res(0);
    For(i,1,n)
    {
        i64 dif = a[i] - ans[i];
        a[i] -= dif; a[i+1] += dif;
        res += dif;
    }
    cout << res << '\n';
    For(i,1,n) cout << ans[i]+i+mn << " \n"[i==n];
}