Milk Sum

题意

有 $N$ 头牛，第 $i$ 头牛每分钟产奶量是 $a_i$ 。

如果第 $k$ 个被移出挤奶机的牛产奶量是 $x$ ，它会贡献 $k\cdot x$ 。为了让总产奶量最大，显然应该让产奶量小的牛先离开，产奶量大的牛后离开。

现在有 $Q$ 个互相独立的询问：如果临时把 $a_i$ 改成 $j$ ，最大总产奶量是多少？

思路

先看一个小数据暴力。每次询问直接修改一个值，重新排序，再计算 $\sum i\cdot a'_i$ 。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:00
 * update_at: 2026-07-11 19:02
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 205;

int n, q;
ll a[MAXN];
ll b[MAXN];

ll calc_answer() {
    for (int i = 1; i <= n; i++) {
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (ll)i * b[i];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cin >> q;
    while (q--) {
        int idx;
        ll val;
        cin >> idx >> val;

        ll old = a[idx];
        a[idx] = val;
        cout << calc_answer() << '\n';
        a[idx] = old;
    }

    return 0;
}

暴力每次都排序，复杂度太高。满分做法只分析“一个元素移动”带来的贡献变化。

先把原数组排序成 b[1..n]，基础答案是：

S=\sum_{i=1}^{n} i\cdot b_i

同时记录原来的第 idx 个数在排序数组中的位置 old_pos。

一次询问把旧值 old_val 改成 val，等价于：

从排序数组中删除 old_pos 位置的旧值；
把新值 val 插入到它应该在的新位置 new_pos。

new_pos 可以用 lower_bound 找到。需要注意：如果 val > old_val，旧值被删除后，新值的插入位置要向左修正一格。

删除旧值后，如果 $new_pos >= old_pos$ ，说明旧值右侧的一段数会整体左移一格：

text

1old_pos + 1 ... new_pos

这些数的系数都减少 1，所以总贡献减少这一段的元素和。

如果 new_pos < old_pos，说明左侧的一段数会整体右移一格：

text

1new_pos ... old_pos - 1

这些数的系数都增加 1，所以总贡献增加这一段的元素和。

区间和用排序数组的前缀和 prefix_sum[] 在 $O(1)$ 内求出，整次询问只剩下二分的 $O(\log N)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:00
 * update_at: 2026-07-11 19:02
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 150005;

int n, q;
ll a[MAXN];       // 原数组，按输入下标保存
ll b[MAXN];       // 排序后的数组
ll prefix_sum[MAXN];
ll base_answer;
int ord[MAXN];    // 原下标的排序顺序
int pos[MAXN];    // pos[i] 表示原第 i 个数在排序数组中的位置

bool cmp_ord(int x, int y) {
    if (a[x] != a[y]) return a[x] < a[y];
    return x < y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
        ord[i] = i;
    }

    sort(ord + 1, ord + n + 1, cmp_ord);
    for (int i = 1; i <= n; i++) {
        pos[ord[i]] = i;
    }

    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i - 1] + b[i];
        base_answer += (ll)i * b[i];
    }

    cin >> q;
    while (q--) {
        int idx;
        ll val;
        cin >> idx >> val;

        int old_pos = pos[idx];
        ll old_val = b[old_pos];

        int new_pos = lower_bound(b + 1, b + n + 1, val) - b;
        if (val > old_val) {
            new_pos--;
        }

        ll ans = base_answer;
        ans -= (ll)old_pos * old_val;

        if (new_pos >= old_pos) {
            // old_pos+1..new_pos 整体向左移动一格，贡献各减去自身值。
            ans -= prefix_sum[new_pos] - prefix_sum[old_pos];
        } else {
            // new_pos..old_pos-1 整体向右移动一格，贡献各增加自身值。
            ans += prefix_sum[old_pos - 1] - prefix_sum[new_pos - 1];
        }

        ans += (ll)new_pos * val;
        cout << ans << '\n';
    }

    return 0;
}

复杂度

预处理排序和前缀和需要 $O(N \log N)$ 。

每个询问一次二分，时间复杂度 $O(\log N)$ 。

总时间复杂度为 $O((N+Q)\log N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的核心是先把最优顺序转化为排序后的贡献公式。

每个查询只改变一个元素，因此不需要重新排序整张表，只要计算删除旧位置、插入新位置时中间区间的整体位移贡献即可。

目录

题意

思路

代码

复杂度

总结