Atcoder Beginner Contest 459 F题题解#

题意：#

给你一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$ 。

你可以对 $A$ 执行下列操作零次或多次：

选择一个有 $1 \le i \le N - 1$ 的整数 $i$ ，将 $A_i$ 减少 $1$ ，并将 $A_{i+1}$ 增加 $1$ 。

求使 $A$ 严格递增所需的最小运算次数。

可以证明答案小于 $2^{63}$ 。

给你 $T$ 个测试用例，请逐个求解。

$1 \le T \le 3 \times 10^5$
$1 \le N \le 2 \times 10^5$
$0 \le A_i \le 10^9$
所有测试用例中 $N$ 的总和最多为 $6 \times 10^5$ 。
所有输入值均为整数。

思路：#

将求严格递增的序列 $B$ 转换为求非递减的序列 $B$ 。

将原序列 $A$ 的每一项转换为 $a_i - i$ 即可。设序列 $B$ 为 $b_i = a_i - i$ ，则 $b_i - b_{i - 1} = a_i - a_{i - 1} - (i - (i - 1))$ ，即 $b_i - b_{i - 1} = a_i - a_{i - 1} - 1$ ，这天然满足严格递增的条件，因此求非递减的序列即可。

将每个数看成一个块，若左边的块的最右端的值大于右边的块的最左端的值，将两个块合并成一个块。在处理每一个块时，需要将块中的值尽可能平均放。

开始时每个块中非递减严格成立。在处理每一个块时，若遇到左边的值的最右端的值大于右边的块的最左端的值，需要合并两个块。此时的情况是需要将左边的值转移至右边，我们就可以尽可能贪心的让左边的值少减一点，即将左端的值最大化，右端的值最小化。在处理每一个块时，我们只需要维护其块内的值的总和和块的长度即可。从左到右遍历块，最后形成一个满足条件的连续的若干个块。

设原序列为 $A$ ，最终序列为 $B$ ，则答案 $ans$ 为： $ans = \sum_{i = 1}^{n} (prefixA_i - prefixB_i)$

设序列 $X$ ，令 $x_i$ 为从第 $i$ 个点到第 $i + 1$ 个点被操作了多少次 $(1 \leq i \leq n - 1)$ ，则 $b_i = a_i + x_{i - 1} - x_i$ 。易得 $x_1 = a_1 - b_1$ ，则 $x_2 = a_2 - b_2 + x_1$ ，即 $x_2 - x_1 = a_2 - b_2$ ，即有： $x_2 = (a_2 - b_2) + (a_1 - b_1)$ ，所以有： $x_i = prefixA_i - prefixB_i$ 。答案便是 $\sum_{i = 1}^{n}x_i$

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4

5
struct node {
6
    int len, sum;
7
    node operator + (const node &other) const {
8
        return node{other.len + len, other.sum + sum};
9
    }
10
};
11

12
int Floor (int a, int b) {
13
    if (a >= 0) return a / b;
14
    return -((-a + b - 1) / b);
15

16
}
17

18
int Ceil (int a, int b) {
19
    return -Floor(-a, b);
20
}
21

22
void solve ()
23
{
24
    int n;
25
    cin >> n;
26
    vector <int> v(n + 1);
27
    for (int i = 1; i <= n; i++) {
28
        cin >> v[i];
29
        v[i] -= i;
30
    }
31

32
    vector <node> st;
33
    for (int i = 1; i <= n; i++) {
34
        st.push_back({1, v[i]});
35
        while (st.size() >= 2) {
36
            node s = st.back();
37
            node t = st[st.size() - 2];
38
            int smn = Floor(s.sum, s.len);
39
            int tmx = Ceil(t.sum, t.len);
40
            if (smn < tmx) {
41
                st.pop_back();
42
                st.pop_back();
43
                st.push_back({s + t});
44
            }else {
45
                break;
46
            }
47
        }
48
    }
49

50
    vector <int> f(n + 1);
51
    int pos = 1;
52

53
    for (auto x : st) {
54
        int mn = Floor(x.sum, x.len);
55
        int cmx = x.sum - mn * x.len;
56
        int cmn = x.len - cmx;
57
        for (int i = 1; i <= cmn; i++) {
58
            f[pos++] = mn;
59
        }
60
        for (int i = 1; i <= cmx; i++) {
61
            f[pos++] = mn + 1;
62
        }
63
    }
64

65
    int ans = 0;
66
    int pv = 0, pf = 0;
67
    for (int i = 1; i <= n - 1; i++) {
68
        pv += v[i];
69
        pf += f[i];
70
        ans += pv - pf;
71
    }
72

73
    cout << ans << '\n';
74
}
75

76
int32_t main ()
77
{
78
    ios::sync_with_stdio(0);
79
    cin.tie(0);
80
    int _ = 1;
81
    cin >> _;
82
    while (_--) {
83
        solve();
84
    }
85
    return 0;
86
}