LG 7078 贪吃蛇

发表于 | 分类于 | 评论数：

摘要

博弈，决策是否 $\max-\min$ ，求终止时间

注意到在终止时没有人后悔，进一步分析单调性

[CSP-S2020] 贪吃蛇

题面

题目描述

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

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

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

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

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

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

题解

首先要读题，搞清楚这个决斗到底是什么东西：

这是每轮 $\max-\min$ 的连续过程， $\max$ 玩家只能选择中止这个过程，而不能改变该过程。

决斗的过程就是不断 $\max-\min$ 至一个元素之过程的前缀。

下一步观察在决斗结束时，活下来的蛇有什么性质，（看反面），注意到死去的蛇注定没有获得过主动权。（否则他会在之前弃权结束掉决斗）进一步分析什么时候第一条有过主动权的蛇成为最弱蛇（称该蛇为关键蛇），如没有这样的蛇，决斗在只有一个幸存者时结束。

在此之前，经历过决斗的蛇都不成为最弱蛇，故而每轮决斗的 $\min$ 单增，以及每轮决斗的 $\max$ 单减是显然的，于是每轮生成的 $\max-\min$ 是单减的，进一步得到关键蛇恰在吃掉最弱蛇后成为最弱蛇。

现在决斗的结束只有两种可能了：关键蛇弃权而不成为最弱蛇，或者关键蛇确信决斗会在下一轮结束而吃掉最弱蛇。

（由于关键蛇必不会死去，决斗不能在此之后终止；又由此，决斗不会在此前结束）

这推出 $\max-\min$ 不成为新的 $\min$ ，则该轮必会进行。

接下来判定决斗是否在下一轮结束，只需要从下一轮为起始再次运用上述结论。但这次我们只关心起始轮会不会发生了：只有吃掉关键蛇的蛇因此成为最弱蛇，我们才需要递归地判定下去。

总结以下前述的分析，决斗将在 $\max-\min$ 不成为新的 $\min$ 时持续下去，判断第一个新 $\min$ 是否会出现，其出现要求从它开始恰有连续偶数轮 $\max-\min$ 成为新的 $\min$ （如新的 $\min$ 是最后一个数，不认为他是新 $\min$ ）

至此我们分析完了此题，只需要模拟决斗的过程并按上述方式进行判断即可。需要维护的是取 $\max$ ，取 $\min$ ，插入一个数；根据前述的 $\max-\min$ 的单调性，可以用一个队列维护新产生的数，复杂度 $\mathcal{O}(n)$

多组数据有点小坑，只有 $T\leq 10$ 组，实际上直接每一组单独做就可以，不必多想。

代码

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
//https://www.luogu.com.cn/problem/P7078
//20211103 nksbwen

#include <cstdio>
#include <cstring>

const int MAXN=1000111;

int T;
int N;

struct Pair{
	int v, id;
};
bool operator < (const Pair &A, const Pair &B){
	return (A.v==B.v)?A.id<B.id:A.v<B.v;
}
bool operator > (const Pair &A, const Pair &B){
	return (A.v==B.v)?A.id>B.id:A.v>B.v;
}
Pair operator - (const Pair &A, const Pair &B){
	return Pair{A.v-B.v, A.id};
}
Pair A[MAXN], B[MAXN], C[MAXN];
int Bl, Br, Cl, Cr;

int Deal(){
	int Tag=0, Tmp;
	while((Br-Bl+1)+(Cr-Cl+1)>1){
		if(Cl>Cr || (Br>=Bl && B[Br]>C[Cl])){
			//max=B[Br];
			if(Cl>Cr || (Br>=Bl && B[Bl]<C[Cr])){
				//min=B[Bl];
				// printf("%d %d %d %d\n", B[Bl].v, B[Bl].id, B[Br].v, B[Br].id);
				C[++Cr]=B[Br--]-B[Bl++];
			}
			else{
				//min=C[Cr];
				C[Cr]=B[Br--]-C[Cr];
			}
		}
		else{
			//max=C[Cl];
			if(Cl>Cr || (Br>=Bl && B[Bl]<C[Cr])){
				//min=B[Bl];
				C[++Cr]=C[Cl++]-B[Bl++];
			}
			else{
				//min=C[Cr];
				C[Cr]=C[Cl++]-C[Cr];
			}
		}
		if((Bl<=Br && C[Cr]>B[Bl]) || (Cl<Cr && C[Cr]>C[Cr-1]) || (Bl>Br && Cl==Cr)){
			if(Tag)	break;
			else	continue;
		}
		else	++Tag;
		if(Tag==1)	Tmp=(Br-Bl+1)+(Cr-Cl+1)+1;
	}
	return (Tag)?(Tmp-!(Tag&1)):1;
}

int main(){
	
	scanf("%d", &T);
	scanf("%d", &N);
	for(int i=1;i<=N;++i){
		scanf("%d", &A[i].v);
		A[i].id=i;
	}
	memcpy(B+1, A+1, sizeof(Pair)*N);Bl=1;Br=N;Cl=1;Cr=0;
	printf("%d\n", Deal());
	for(int i=1, k;i<T;++i){
		scanf("%d", &k);
		for(int j=1, a, b;j<=k;++j){
			scanf("%d%d", &a, &b);
			A[a].v=b;
		}
		memcpy(B+1, A+1, sizeof(Pair)*N);Bl=1;Br=N;Cl=1;Cr=0;
		printf("%d\n", Deal());
	}
	
	return 0;
}