[CSP-S 2020] 贪吃蛇

GitHub 跳转原题关系图返回列表

用双队列模拟强弱顺序，先处理必吃局面，再用递归反推第一次冒险吃是否成立。

OJ: luogu

题目 ID: P7078

难度:提高+/省选-

标签:贪心博弈双端队列模拟

日期: 2026-07-06 08:46

题意

有 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112// brute.cpp：小数据完整博弈搜索，判断最强蛇吃后自己是否还能存活。
#include <bits/stdc++.h>
using namespace std;

struct Snake {
    long long value;
    int id;
};

int T, n;
long long a[20];
map<string, vector<Snake> > memo_alive;

bool weaker_than(const Snake &a, const Snake &b) {
    if (a.value != b.value) {
        return a.value < b.value;
    }
    return a.id < b.id;
}

string encode_state(const vector<Snake> &state) {
    string key;
    for (int i = 0; i < (int)state.size(); i++) {
        key += to_string(state[i].id);
        key += ':';
        key += to_string(state[i].value);
        key += ',';
    }
    return key;
}

bool contains_id(const vector<Snake> &alive, int id) {
    for (int i = 0; i < (int)alive.size(); i++) {
        if (alive[i].id == id) {
            return true;
        }
    }
    return false;
}

vector<Snake> play_game(vector<Snake> state) {
    sort(state.begin(), state.end(), weaker_than);
    string key = encode_state(state);
    auto it = memo_alive.find(key);
    if (it != memo_alive.end()) {
        return it->second;
    }

    if ((int)state.size() == 1) {
        memo_alive[key] = state;
        return state;
    }

    Snake weakest = state.front();
    Snake strongest = state.back();

    vector<Snake> next_state;
    for (int i = 1; i + 1 < (int)state.size(); i++) {
        next_state.push_back(state[i]);
    }
    Snake changed;
    changed.value = strongest.value - weakest.value;
    changed.id = strongest.id;
    next_state.push_back(changed);

    vector<Snake> alive_after_eat = play_game(next_state);
    if (contains_id(alive_after_eat, strongest.id)) {
        memo_alive[key] = alive_after_eat;
    } else {
        memo_alive[key] = state;
    }
    return memo_alive[key];
}

int solve_current_case() {
    vector<Snake> state;
    for (int i = 1; i <= n; i++) {
        Snake x;
        x.value = a[i];
        x.id = i;
        state.push_back(x);
    }
    memo_alive.clear();
    vector<Snake> alive = play_game(state);
    return (int)alive.size();
}

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

    cin >> T;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cout << solve_current_case() << '\n';

    for (int tc = 2; tc <= T; tc++) {
        int k;
        cin >> k;
        for (int i = 1; i <= k; i++) {
            int x;
            long long y;
            cin >> x >> y;
            a[x] = y;
        }
        cout << solve_current_case() << '\n';
    }

    return 0;
}

满分做法要利用两个结论。

第一个结论：如果最强蛇 x 吃掉最弱蛇 y 后，新的 x-y 不是当前最弱蛇，那么 x 一定会吃。直观理解是：它吃完以后前面至少还有更弱的蛇替它挡刀；后面无论谁停手或继续吃，它都不会因为这一次操作立即变成最危险的目标。

第二个结论：如果 x-y 变成了最弱蛇，那么 x 是否敢吃，要看下一条最强蛇会不会吃它。下一条蛇如果吃完后也变成最弱蛇，又要继续看再下一条蛇。于是这一段是一个递归反推：

text

1
2下一条蛇会吃  -> 当前蛇不敢吃
下一条蛇不吃  -> 当前蛇敢吃

实现分成两步：

先不断执行第一类“必吃”操作，直到某次吃完会变成最弱蛇，或者只剩一条蛇；
对剩余局面做一次递归判断，看这一次“冒险吃”能不能发生。

因为输入保证体力值不降，原始蛇天然有序。吃出来的新蛇也可以用另一个双端队列维护。每次取全局最弱、最强时，只需要比较两个队列的队首或队尾。

代码

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204// main.cpp：双队列维护强弱顺序，先处理必吃局面，再递归判断冒险吃。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

struct Snake {
    long long value;
    int id;
    int from_queue;
};

int T, n;
long long a[MAXN];
Snake q1[MAXN * 2], q2[MAXN * 2];
int l1, r1, l2, r2;
int eaten_count;

bool weaker_than(const Snake &a, const Snake &b) {
    if (a.value != b.value) {
        return a.value < b.value;
    }
    return a.id < b.id;
}

bool stronger_than(const Snake &a, const Snake &b) {
    if (a.value != b.value) {
        return a.value > b.value;
    }
    return a.id > b.id;
}

Snake get_min_snake() {
    Snake result;
    if (l1 <= r1 && l2 <= r2) {
        if (weaker_than(q1[l1], q2[l2])) {
            result = q1[l1++];
        } else {
            result = q2[l2++];
        }
    } else if (l1 <= r1) {
        result = q1[l1++];
    } else {
        result = q2[l2++];
    }
    return result;
}

Snake get_max_snake() {
    Snake result;
    if (l1 <= r1 && l2 <= r2) {
        if (stronger_than(q1[r1], q2[r2])) {
            result = q1[r1--];
        } else {
            result = q2[r2--];
        }
    } else if (l1 <= r1) {
        result = q1[r1--];
    } else {
        result = q2[r2--];
    }
    return result;
}

void push_back_original(const Snake &x) {
    q1[++r1] = x;
}

void push_front_original(const Snake &x) {
    q1[--l1] = x;
}

void push_back_new(const Snake &x) {
    q2[++r2] = x;
}

void push_front_new(const Snake &x) {
    q2[--l2] = x;
}

void restore_front(const Snake &x) {
    if (x.from_queue == 1) {
        push_front_original(x);
    } else {
        push_front_new(x);
    }
}

void restore_back(const Snake &x) {
    if (x.from_queue == 1) {
        push_back_original(x);
    } else {
        push_back_new(x);
    }
}

Snake make_after_eat(const Snake &strongest, const Snake &weakest) {
    Snake result;
    result.value = strongest.value - weakest.value;
    result.id = strongest.id;
    result.from_queue = 2;
    return result;
}

// 判断 strongest 吃 weakest 后是否一定不是当前最弱蛇。
bool after_eat_not_weakest(const Snake &strongest, const Snake &weakest, const Snake &second_min) {
    Snake changed = make_after_eat(strongest, weakest);
    return stronger_than(changed, second_min);
}

void solve_forced_part() {
    while (n - eaten_count > 1) {
        Snake strongest = get_max_snake();
        Snake weakest = get_min_snake();
        Snake second_min = get_min_snake();

        if (after_eat_not_weakest(strongest, weakest, second_min)) {
            eaten_count++;
            Snake changed = make_after_eat(strongest, weakest);

            // 新蛇在这一阶段不会成为最弱；为了维持双队列顺序，先放新蛇，再还回第二弱蛇。
            push_front_new(changed);
            restore_front(second_min);
        } else {
            restore_back(strongest);
            restore_front(second_min);
            restore_front(weakest);
            return;
        }
    }
}

bool can_eat_in_risky_part(int alive_count) {
    if (alive_count <= 1) {
        return false;
    }
    if (alive_count == 2) {
        return true;
    }

    Snake strongest = get_max_snake();
    Snake weakest = get_min_snake();
    Snake second_min = get_min_snake();

    if (after_eat_not_weakest(strongest, weakest, second_min)) {
        return true;
    }

    Snake changed = make_after_eat(strongest, weakest);
    restore_front(second_min);
    push_front_new(changed);

    // 如果下一条蛇会吃掉它，那么当前蛇就不能冒险；否则当前蛇可以吃。
    return !can_eat_in_risky_part(alive_count - 1);
}

int solve_current_case() {
    l1 = MAXN;
    r1 = MAXN - 1;
    l2 = MAXN;
    r2 = MAXN - 1;
    eaten_count = 0;

    for (int i = 1; i <= n; i++) {
        Snake x;
        x.value = a[i];
        x.id = i;
        x.from_queue = 1;
        push_back_original(x);
    }

    solve_forced_part();
    if (can_eat_in_risky_part(n - eaten_count)) {
        eaten_count++;
    }

    return n - eaten_count;
}

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

    cin >> T;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cout << solve_current_case() << '\n';

    for (int tc = 2; tc <= T; tc++) {
        int k;
        cin >> k;
        for (int i = 1; i <= k; i++) {
            int x;
            long long y;
            cin >> x >> y;
            a[x] = y;
        }
        cout << solve_current_case() << '\n';
    }

    return 0;
}

复杂度

每条蛇在一次测试数据中最多被取出、放入常数次。

单组时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。多组数据在修改体力值后重新计算，整体为 $O(Tn + 修改数)$ 。

总结

本题的难点不是维护最大最小，而是判断“最强蛇是否敢吃”。只要抓住“吃完不是最弱就必吃；吃完变最弱就递归看下一条蛇”的博弈结构，剩下就是双端队列模拟。

对拍时，brute.cpp 使用完整博弈递归搜索，可以验证小数据下双队列结论的实现是否正确。

P7078 [CSP-S 2020] 贪吃蛇

题目描述

草原上有 $n$ 条蛇，编号分别为 $1, 2, \ldots , n$ 。初始时每条蛇有一个体力值 $a_i$ ，我们称编号为 $x$ 的蛇实力比编号为 $y$ 的蛇强当且仅当它们当前的体力值满足 $a_x > a_y$ ，或者 $a_x = a_y$ 且 $x > y$ 。

接下来这些蛇将进行决斗，决斗将持续若干轮，每一轮实力最强的蛇拥有选择权，可以选择吃或者不吃掉实力最弱的蛇：

如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。
如果选择不吃，决斗立刻结束。

每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇（显然，蛇不会选择吃自己）。

现在假设每条蛇都足够聪明，请你求出决斗结束后会剩几条蛇。

本题有多组数据，对于第一组数据，每条蛇体力会全部由输入给出，之后的每一组数据，会相对于上一组的数据，修改一部分蛇的体力作为新的输入。

输入格式

第一行一个正整数 $T$ ，表示数据组数。
接下来有 $T$ 组数据，对于第一组数据，第一行一个正整数 $n$ ，第二行 $n$ 个非负整数表示 $a_i$ 。
对于第二组到第 $T$ 组数据，每组数据：
第一行第一个非负整数 $k$ 表示体力修改的蛇的个数。
第二行 $2k$ 个整数，每两个整数组成一个二元组 $(x,y)$ ，表示依次将 $a_x$ 的值改为 $y$ 。一个位置可能被修改多次，以最后一次修改为准。

输出格式

输出 $T$ 行，每行一个整数表示最终存活的蛇的条数。

输入输出样例 #1

输入 #1

text

1
2
3
4
52
3
11 14 14
3
1 5 2 6 3 25

输出 #1

text

1
23
1

输入输出样例 #2

输入 #2

text

1
2
3
4
52
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50

输出 #2

text

1
25
3

输入输出样例 #3

输入 #3

text

1见附件中的 snakes/snakes3.in

输出 #3

text

1见附件中的 snakes/snakes3.ans

输入输出样例 #4

输入 #4

text

1见附件中的 snakes/snakes4.in

输出 #4

text

1见附件中的 snakes/snakes4.ans

说明/提示

【样例 #1 解释】

第一组数据，第一轮中 $3$ 号蛇最强， $1$ 号蛇最弱。若 $3$ 号蛇选择吃，那么它将在第二轮被 $2$ 号蛇吃掉。因此 $3$ 号蛇第一轮选择不吃， $3$ 条蛇都将存活。

对于第二组数据， $3$ 条蛇体力变为 $5, 6, 25$ 。第一轮中 $3$ 号蛇最强， $1$ 号蛇最弱，若它选择吃，那么 $3$ 号蛇体力值变为 $20$ ，在第二轮中依然是最强蛇并能吃掉 $2$ 号蛇，因此 $3$ 号蛇会选择两轮都吃，最终只有 $1$ 条蛇存活。

【数据范围】

对于 $20 \%$ 的数据， $n = 3$ 。
对于 $40 \%$ 的数据， $n \le 10$ 。
对于 $55 \%$ 的数据， $n \le 2000$ 。
对于 $70\%$ 的数据， $n \le 5 \times {10}^4$ 。
对于 $100\%$ 的数据： $3 \le n \le {10}^6$ ， $1 \le T \le 10$ ， $0 \le k \le {10}^5$ ， $0 \le a_i, y \le 10^9$ 。保证每组数据（包括所有修改完成后的）的 $a_i$ 以不降顺序排列。

[CSP-S 2020] 贪吃蛇

目录

题意

思路

代码

复杂度

总结