[CSP-S 2020] 贪吃蛇

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

用双队列维护强弱顺序，先处理必吃局面，再递归判断冒险吃。

OJ: luogu

题目 ID: P7078

难度:提高+/省选-

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

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

有 $n$ 条蛇，第 $i$ 条蛇有体力值 $a_i$ 和编号 $i$ 。强弱比较规则：体力值大者强；体力值相同则编号大者强。

决斗进行若干轮。每轮由当前最强蛇决定是否吃掉当前最弱蛇：若吃，最强蛇的体力值减去最弱蛇的体力值，最弱蛇退出，决斗继续；若不吃，决斗立刻结束。每条蛇的目标是：先保证自己不被吃，在此前提下尽量多吃别的蛇。

求决斗结束时存活蛇的数量。有多组测试数据，每组在上一组的体力值上做若干单点修改后重新求解。

解法路线

题面按数据规模给分： $n = 3$ 得 20 分， $n \leqslant 10$ 得 40 分， $n \leqslant 2000$ 得 55 分， $n \leqslant 5 \times 10^4$ 得 70 分， $n \leqslant 10^6$ 得 100 分。三层解法与档位对应：

暴力解法（20/40 分档）：完全按题面规则递归模拟决斗，不加任何结论。
子任务解法（55/70 分档）：证明两条贪心结论，把"敢不敢吃"变成一条递归判断链，用 std::set 维护强弱顺序。
正解（100 分档）：复用同样的贪心结论，用双队列代替有序集合，把单组复杂度降到 $O(n)$ 。

后一层直接复用前一层的观察，依次消除的瓶颈是"暴力搜索"和"取最大最小的容器开销"。正式主解是 main.cpp。

暴力解法：直接模拟决斗（20/40 分档）

适用范围

$n \leqslant 10$ 。数据再大时递归层数与状态规模都会超时。

思路

直接翻译题面规则：当前最强蛇先假设自己吃掉最弱蛇，然后递归看它在后续游戏中是否还能存活。如果能存活，它就会吃（多吃一条总是更优）；否则它会停手，决斗结束。

代码

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/**
 * 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-10-01 22:33
 * update_at: 2026-10-01 22:33
 */
// subtask_40.cpp：20/40 分档（n <= 10）解法。完全按题面规则递归模拟决斗：
// 最强蛇若吃掉最弱蛇后自己仍能存活到最后就吃，否则选择不吃、决斗立刻结束。
// 不依赖任何贪心结论，直接翻译题面规则，适合小数据。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 15;

struct Snake {
    ll value;
    int id;
};

int T, n;
ll a[MAXN]; // a[i]：第 i 条蛇的体力值

// 比较两条蛇的强弱：体力值大者强，相同则编号大者强。
// 参数用 x/y，避开全局体力值数组 a[]。
bool weaker_than(const Snake &x, const Snake &y) {
    if (x.value != y.value) {
        return x.value < y.value;
    }
    return x.id < y.id;
}

// 判断编号为 id 的蛇是否在存活集合中。
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);
    if ((int)state.size() == 1) {
        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)) {
        return alive_after_eat; // 吃了能活到最后，就吃
    }
    return state; // 吃了会死，选择不吃，决斗结束
}

// 求解单组测试数据，返回最终存活蛇的数量。
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);
    }
    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;
            ll y;
            cin >> x >> y;
            a[x] = y;
        }
        cout << solve_current_case() << '\n';
    }

    return 0;
}

对拍时使用等价的带记忆化实现 brute.cpp，两者决策逻辑相同。

复杂度与瓶颈

每层递归排序一次当前存活集合，递归深度 $O(n)$ ，单组 $O(n^2 \log n)$ 。瓶颈：没有利用任何决策规律， $n$ 稍大就慢，无法处理 $n = 10^6$ 。

子任务解法：贪心结论 + 有序集合（55/70 分档）

适用范围

$n \leqslant 5 \times 10^4$ 。 $n = 10^6$ 时 std::set 的对数常数偏大。

思路

这一层的关键是两条贪心结论。

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

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

text

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

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

容器用 std::set 存所有存活蛇，(体力值, 编号) 升序即从弱到强，取最大最小都是 $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
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/**
 * 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-10-01 22:33
 * update_at: 2026-10-01 22:33
 */
// subtask_55.cpp：55/70 分档解法。先用两条贪心结论把"敢不敢吃"理清
// （吃完不是最弱必吃；吃完变最弱则递归看下一条蛇敢不敢吃），
// 再用 std::set 维护强弱顺序，单组 O(n log n)。n <= 1e6 时建议换双队列 O(n)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// (体力值, 编号) 升序即从弱到强：体力值小者弱，相同则编号小者弱。
typedef pair<ll, int> Snake;

int T, n;
ll a[1000005];  // a[i]：第 i 条蛇的体力值
set<Snake> alive; // 当前存活的蛇，begin() 最弱，rbegin() 最强
int eaten_count;  // 已经被吃掉的蛇的数量

// 取出当前最弱蛇。
Snake get_min_snake() {
    Snake result = *alive.begin();
    alive.erase(alive.begin());
    return result;
}

// 取出当前最强蛇。
Snake get_max_snake() {
    set<Snake>::iterator it = alive.end();
    it--;
    Snake result = *it;
    alive.erase(it);
    return result;
}

// 最强蛇吃掉最弱蛇后生成的新蛇：体力值相减，编号保留。
Snake make_after_eat(const Snake &strongest, const Snake &weakest) {
    return make_pair(strongest.first - weakest.first, strongest.second);
}

// 判断 strongest 吃 weakest 后，新蛇是否一定不是当前最弱蛇（即可安全吃）。
bool after_eat_not_weakest(const Snake &strongest, const Snake &weakest, const Snake &second_min) {
    return make_after_eat(strongest, weakest) > second_min;
}

// 第一阶段：处理所有"必吃"局面。
// 只剩两条时不进循环（见 solve_current_case 的特判），保证取第二弱时集合非空。
void solve_forced_part() {
    while ((int)alive.size() > 2) {
        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++;
            alive.insert(make_after_eat(strongest, weakest));
            alive.insert(second_min);
        } else {
            // 吃完会变最弱：把取出来的三条还回去，交给冒险阶段递归判断。
            alive.insert(strongest);
            alive.insert(second_min);
            alive.insert(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;
    }

    alive.insert(second_min);
    alive.insert(make_after_eat(strongest, weakest));
    return !can_eat_in_risky_part(alive_count - 1);
}

// 求解单组测试数据，返回最终存活蛇的数量。
int solve_current_case() {
    alive.clear();
    eaten_count = 0;
    for (int i = 1; i <= n; i++) {
        alive.insert(make_pair(a[i], i));
    }

    solve_forced_part();

    int alive_count = (int)alive.size();
    if (alive_count == 2) {
        // 只剩两条：最强吃最弱后独自存活，必吃。
        eaten_count++;
    } else if (can_eat_in_risky_part(alive_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;
            ll y;
            cin >> x >> y;
            a[x] = y;
        }
        cout << solve_current_case() << '\n';
    }

    return 0;
}

复杂度与瓶颈

必吃阶段每条蛇进出集合常数次， $O(n \log n)$ ；冒险递归深度 $O(n)$ ，每层 $O(\log n)$ 。单组 $O(n \log n)$ 。瓶颈：有序集合常数大， $n = 10^6$ 时不够快。

正解：双队列线性扫描（100 分档）

关键观察

输入保证 $a_i$ 以不降顺序给出（修改后依然不降），所以初始所有蛇天然是有序的；吃出来的新蛇也能用另一个双端队列维护，不会打乱两个队列各自的有序性。于是"取全局最弱、最强"不需要平衡树，只要比较两个队列的队首或队尾。

思路

贪心结论与上一层完全相同，只换容器：原始蛇放队列 1，吃出来的新蛇放队列 2，两个队列都按从弱到强排列。

取最弱：比较两队列队首，取较弱者；
取最强：比较两队列队尾，取较强者；
吃完生成的新蛇放队列 2 的弱端，被还回的第二弱蛇放回原队列弱端。

因为每次都在当前约束下做最优决策，前面数字的最优选择不会被后面破坏。每条蛇在一次测试数据中最多被取出、放入常数次，单组 $O(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
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227/**
 * 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-10-01 21:11
 * update_at: 2026-10-01 22:33
 */
// main.cpp：双队列维护强弱顺序，先处理必吃局面，再递归判断冒险吃。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1000005;

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

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

// 比较两条蛇的强弱：体力值大者强，相同则编号大者强。
// 参数用 x/y，避开全局体力值数组 a[]。
bool weaker_than(const Snake &x, const Snake &y) {
    if (x.value != y.value) {
        return x.value < y.value;
    }
    return x.id < y.id;
}

bool stronger_than(const Snake &x, const Snake &y) {
    if (x.value != y.value) {
        return x.value > y.value;
    }
    return x.id > y.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);
}

// 第一阶段：处理所有"必吃"局面。
// 若最强蛇吃完后不是最弱，则它一定会吃，继续循环。
// 只剩两条时不进循环（见 solve_current_case 的特判），保证取第二弱时队列非空。
void solve_forced_part() {
    while (n - eaten_count > 2) {
        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();
    int alive_count = n - eaten_count;
    if (alive_count == 2) {
        // 只剩两条：最强吃最弱后独自存活，必吃。
        eaten_count++;
    } else if (can_eat_in_risky_part(alive_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;
            ll y;
            cin >> x >> y;
            a[x] = y;
        }
        cout << solve_current_case() << '\n';
    }

    return 0;
}

复杂度

时间复杂度：单组 $O(n)$ 。多组数据在修改体力值后重新计算，整体为 $O(Tn + \text{修改数})$ 。
空间复杂度： $O(n)$ ，两个双端队列各开 $2n$ 的容量。

总结

本题的难点不是维护最大最小，而是判断"最强蛇是否敢吃"。只要抓住"吃完不是最弱就必吃；吃完变最弱就递归看下一条蛇"的博弈结构，剩下就是容器选型：std::set 足够 55/70 分档，双端队列利用输入有序性把 100 分档做到 $O(n)$ 。

对拍时，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] 贪吃蛇

目录

形式化题目

解法路线

暴力解法：直接模拟决斗（20/40 分档）

适用范围

思路

代码

复杂度与瓶颈

子任务解法：贪心结论 + 有序集合（55/70 分档）

适用范围

思路

代码

复杂度与瓶颈

正解：双队列线性扫描（100 分档）

关键观察

思路

代码

复杂度

总结