Milk Exchange

形式化题目

给定一个环形序列，每个位置初始有 $a_i$ 单位资源。每轮每个非空位置按给定方向向相邻位置转移 $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$ 升。如果它收到 $0$ 或 $1$ 升，就不会产生额外损失；只有它同时被左右两边指向时，才可能收到 $2$ 升、送出 $1$ 升，多出来的部分因为桶满而损失。

哪些位置会同时被左右两边指向？

相邻的 R L 会形成一个汇合处：左边的 R 点可能被左侧连续 R 链推来额外牛奶，右边的 L 点可能被右侧连续 L 链推来额外牛奶。

这张图展示一个局部结构：

text

1
2
3
4
5... R R R L L L ...
        ^ ^
        | |
        | `- 右边 L 点：右侧连续 L 链会把牛奶推到这里
        `--- 左边 R 点：左侧连续 R 链会把牛奶推到这里

中间相邻的 R L 是两个可能溢出的点。R L 之外的长链内部只是单向传递，链内不会凭空损失。

为什么只需要统计两侧供奶链？

以左边的 R 溢出点为例：

text

1
2
3
4
5左侧连续 R 链        溢出点       右邻点
R  R  R  R            R           L
---------->           ^
这些牛奶最多          |
一路向右推到这里      这里每分钟最多额外损失 1 升

左侧连续 R 链上的牛奶都沿同一个方向向右流动，链内不会损失。它最多能让汇合点损失整条链的容量和；同时每分钟最多损失 $1$ 升，所以 $M$ 分钟内最多损失 $M$ 升。

因此一条供奶链对总答案的扣减是：

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

右边 L 点完全对称：统计它右侧连续 L 链的容量和，再扣掉 $\min(\text{链容量和}, M)$ 。

为什么每条链不会被重复统计？

两个不同的 RL 汇合处之间，方向一定会发生分界。每一段连续的 R 或连续的 L 只会贴着某一个 RL 汇合处的一侧，因此这些供奶链互不重叠。

text

1
2
3
4
5
6R R R L L R R L L L
    ^ ^     ^ ^
    | |     | |
    | |     | `-- 第二个 RL 的右侧 L 链
    | `-------- 第一个 RL 的右侧 L 链
    `---------- 第一个 RL 的左侧 R 链

所以从初始总容量开始，把所有供奶链造成的损失相加扣掉，就是最终剩余总量。

做法：

答案初始化为 $\sum a_i$ 。
枚举每个位置 $i$ ，如果 $s_i=R$ 且 $s_{i+1}=L$ ，就找到一个 RL 汇合处。
对左边 R 点，向左统计连续 R 链容量和，扣掉 $\min(\text{链和}, M)$ 。
对右边 L 点，向右统计连续 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/**
 * 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-08-10 21:51
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
long long m;
string direction;
long long capacity[MAXN]; // capacity[i]：第 i 头奶牛桶的容量，也就是初始牛奶量

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;
}

char dir_at(int x) {
    return direction[x - 1];
}

// 对于 RL 中左边的 R 点，统计它左侧连续 R 链的容量和，不包含这个溢出点本身。
long long sum_left_r_chain(int pos) {
    long long sum = 0;
    int cur = pre_pos(pos);
    while (dir_at(cur) == 'R') {
        sum += capacity[cur];
        cur = pre_pos(cur);
    }
    return sum;
}

// 对于 RL 中右边的 L 点，统计它右侧连续 L 链的容量和，不包含这个溢出点本身。
long long sum_right_l_chain(int pos) {
    long long sum = 0;
    int cur = next_pos(pos);
    while (dir_at(cur) == 'L') {
        sum += capacity[cur];
        cur = next_pos(cur);
    }
    return sum;
}

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

    cin >> n >> m;
    cin >> direction;

    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        cin >> capacity[i];
        answer += capacity[i];
    }

    for (int i = 1; i <= n; i++) {
        int j = next_pos(i);
        if (dir_at(i) == 'R' && dir_at(j) == 'L') {
            long long left_loss = sum_left_r_chain(i);
            long long right_loss = sum_right_l_chain(j);

            answer -= min(left_loss, m);
            answer -= min(right_loss, m);
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

每头奶牛只会被某个相邻 RL 的一侧供奶链统计一次。时间复杂度 $O(N)$ ，空间复杂度 $O(N)$ 。

总结

这题的关键是换统计对象：不要模拟每一分钟的完整状态，而是只统计总量会在哪里损失。只有相邻 RL 汇合处会产生溢出，每侧损失由单向供奶链容量和与时间 $M$ 的较小值决定。

目录

形式化题目

思路

代码

复杂度

总结