CSPS2020贪吃蛇题解

原题链接：725.贪吃蛇

超级小帅童

2024-10-21 21:42:10

发布于：广东

35阅读

0回复

0点赞

温馨提示：思路来自洛谷题解，并非本人.

祝大家CSP考试顺利！
这道题的主要思路如下：

1.看最强的蛇吃完后会不会变成最弱的蛇.

如果不会变成最弱的蛇，就放心吃，因为吃完后下一条最强的蛇肯定比原来的它弱，而最弱的蛇肯定比原来的强，所以一定不会吃到它.

2.如果吃了后会成最弱的蛇，那就要复杂的考虑了（本题的最难点）：

它就得考虑下一条蛇吃完它后会不会变成最弱的蛇，如果不会就不吃，否则又得考虑下下一条蛇吃完下一条蛇会不会变成最弱的蛇，如果不会那下一条蛇就不吃，那它就可以放心吃，否则又得考虑下下下一条蛇……
~~开始递归了~~

简单点说就是一直判断，直到有一条蛇可以放心吃了为止（判断奇偶性）.

由于这里的时限只有1s，所以不能用洛谷能过的set来做了.

我们可以用双端队列来做这题
建立两个双端队列 $q1,q2$ ， $q1$ 存储初始的有序蛇，如果吃了以后不是最弱的，就存进 $q2$ 的头部，让 $q2$ 也满足单调性。
最大值的话在 $q1,q2$ 找就行了.

#include <iostream>
#include <cstdio>
#include <deque> 
using namespace std;
int a[1000005], n;
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
//找最大值
#define get_max if(q2.empty() || !q1.empty() && q1.back() > q2.back()){\
	x = q1.back().first, id = q1.back().second, q1.pop_back();\
}else x = q2.back().first, id = q2.back().second, q2.pop_back();
int solve(){
	deque <pair <int, int>> q1, q2;
	for(int i = 1; i <= n; i++){
		q1.push_back({a[i], i});
	}
	while(1){
		if(q1.size() + q2.size() == 2) return 1;
		int x, y, id;
		y = q1.front().first, q1.pop_front();
		get_max;
		pair <int, int> cur = {x - y, id};
		if(q1.empty() || q1.front() > cur){//吃完后是最弱的
			int ans = q1.size() + q2.size() + 2, ct = 0;
			while(1){//按题意递归
				ct ^= 1;
				if(q1.size() + q2.size() == 1){
					if(!ct) ans--;
					return ans;
				}
				get_max;
				cur = {x - cur.first, id};
				if(!q1.empty() && cur >= q1.front() || !q2.empty() && cur >= q2.front()){
					if(!ct) ans--;
					return ans;
				}
			}
		}else q2.push_front(cur);//否则就吃
	}
}
int main(){
	int t = read();
	bool flag = 0;
	while(t--){
		if(flag){
			int k = read(), x, y;
			for(int i = 1; i <= k; i++){
				x = read(), y = read();
				a[x] = y;
			}
		}else{
			n = read();
			for(int i = 1; i <= n; i++) a[i] = read();
			flag = 1;
		}
		cout << solve() << endl;
	}

	return 0;
}