Milk Exchange

题意

有 $N$ 头奶牛围成一圈，第 $i$ 头奶牛的桶容量是 $a_i$ ，初始时每个桶都是满的。

每一分钟同时发生：

如果一头奶牛桶里至少有 $1$ 升牛奶，她会按 L 或 R 向相邻奶牛传出 $1$ 升。
如果某个桶收到牛奶后超过容量，超过的部分会损失。

求 $M$ 分钟后所有桶里还剩多少牛奶。

思路

先看一个可以直接按题意验证的小数据模拟：

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/**
 * 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 15:57
 * update_at: 2026-07-11 15:59
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;

int n;
long long m;
string str;
char s[MAXN];
long long cap_arr[MAXN]; // 每个桶的容量
long long cur[MAXN];     // 当前牛奶量
long long nxt[MAXN];     // 下一分钟牛奶量

int pre_pos(int x) {
    if (x == 1) return n;
    return x - 1;
}

int next_pos(int x) {
    if (x == n) return 1;
    return x + 1;
}

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

    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= n; i++) {
        s[i] = str[i - 1];
    }

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

    // 小数据直接逐分钟模拟同时传奶。
    for (long long t = 1; t <= m; t++) {
        for (int i = 1; i <= n; i++) {
            nxt[i] = cur[i];
        }

        for (int i = 1; i <= n; i++) {
            if (cur[i] == 0) continue;
            nxt[i]--;
            if (s[i] == 'L') {
                nxt[pre_pos(i)]++;
            } else {
                nxt[next_pos(i)]++;
            }
        }

        for (int i = 1; i <= n; i++) {
            cur[i] = min(nxt[i], cap_arr[i]);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += cur[i];
    }

    cout << ans << '\n';

    return 0;
}

暴力每一分钟复制当前状态，再统一处理所有奶牛的传奶，最后把每个桶限制在容量以内。它的复杂度是 $O(NM)$ ，而本题 $N,M$ 都可能很大，不能逐分钟模拟。

关键是找“什么时候会损失牛奶”。

如果一头奶牛每分钟送出 $1$ 升、收到 $1$ 升，总量不变，不会额外损失。只有当它同时被左右两边指向时，才可能每分钟收到 $2$ 升、送出 $1$ 升，多出来的牛奶因为桶满而损失。

这种位置只会出现在相邻的 RL 附近：

text

1
2... R R R L L L ...
        ^ ^

中间这对相邻的 R L 是两个可能溢出的点。左边那个 R 点的额外牛奶来自它左侧连续的 R 链；右边那个 L 点的额外牛奶来自它右侧连续的 L 链。

以左边这个 R 点为例：

位置关系	方向	是否计入左侧供奶链
更左侧连续若干点	`R`	是
当前 `R` 点	`R`	否，它是溢出点
右邻点	`L`	否，它属于另一侧

一条供奶链上的牛奶只沿一个方向流动，链内不会凭空损失。它最多能让汇合点损失这条链的容量总和；但每分钟最多损失 $1$ 升，所以 $M$ 分钟内最多损失 $M$ 升。

于是每条供奶链对答案的扣减是：

\min(\text{链上容量和}, M)

做法：

先把答案初始化为 $\sum a_i$ 。
枚举每个相邻位置，如果出现 R L，标记这两个可能溢出的点。
对每个左侧溢出点，向左找连续 R 链，扣掉 $\min(\text{链和}, M)$ 。
对每个右侧溢出点，向右找连续 L 链，扣掉 $\min(\text{链和}, M)$ 。

所有这样的链互不重叠，总扫描量是线性的。

代码

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
81
82
83
84
85
86
87
88
89
90
91
92/**
 * 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 15:57
 * update_at: 2026-07-11 15:59
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
long long m;
string str;
char s[MAXN];
long long a[MAXN];
bool loss_left[MAXN];  // loss_left[i]：i 是一段 R 链右端的亏损点
bool loss_right[MAXN]; // loss_right[i]：i 是一段 L 链左端的亏损点

int pre_pos(int x) {
    if (x == 1) return n;
    return x - 1;
}

int next_pos(int x) {
    if (x == n) return 1;
    return x + 1;
}

long long calc_left_chain(int pos) {
    long long sum = 0;
    int j = pre_pos(pos);
    while (s[j] == 'R') {
        sum += a[j];
        j = pre_pos(j);
    }
    return sum;
}

long long calc_right_chain(int pos) {
    long long sum = 0;
    int j = next_pos(pos);
    while (s[j] == 'L') {
        sum += a[j];
        j = next_pos(j);
    }
    return sum;
}

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

    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= n; i++) {
        s[i] = str[i - 1];
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += a[i];
        loss_left[i] = false;
        loss_right[i] = false;
    }

    // 相邻的 R L 会形成两个可能溢出的点。
    for (int i = 1; i <= n; i++) {
        int j = next_pos(i);
        if (s[i] == 'R' && s[j] == 'L') {
            loss_left[i] = true;
            loss_right[j] = true;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (loss_left[i]) {
            long long sum = calc_left_chain(i);
            ans -= min(sum, m);
        }
        if (loss_right[i]) {
            long long sum = calc_right_chain(i);
            ans -= min(sum, m);
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

每头奶牛只会被相邻 RL 的某一侧链统计一次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

这题不要盯着“每一分钟怎么变化”，而要盯着“牛奶到底在哪里损失”。

只有相邻 RL 汇合处可能溢出，损失量由两侧单向供奶链决定，再用 $M$ 截断即可。

目录

题意

思路

代码

复杂度

总结