C. Fighting Tournament（模拟/map）

题目

题意

给定n个选手，每个选手有一个权值，且每个选手的权值取值各不相同，且范围为1到n。
即这n个选手的权值a[i]是一个关于n的排列。

两个选手进行比赛，权值大的那位选手获胜。

对于每轮比赛，做以下操作：

选择当前最前面两位选手，进行比赛。获胜的选手，排在第1位；失败的选手，排在最后1位。

例如5位选手，他们的权值为 3 1 4 5 2

第1轮，第1位选手和第2位选手比赛，第1位选手获胜，此时数组为 3 4 5 2 1

第2轮，第2位选手和第3位选手比赛，第3位选手获胜，此时数组为 4 5 2 1 3

第3轮，第3位选手和第4位选手比赛，第4位选手获胜，此时数组为 5 2 1 3 4

第4轮，第4位选手和第5位选手比赛，第4位选手获胜，此时数组为 5 1 3 4 2

第5轮，第4位选手和第2位选手比赛，第4位选手获胜，此时数组为 5 3 4 2 1
…

有q次询问，对于第i个选手，经过前k轮后，他总共获胜了多少次。

1<=n,q<=100000

思路

这里查询次数多，我们需要考虑优化，不能直接模拟。

观察发现，当权值为n的选手走到了前2位后，那么其他人只有刷经验值的份了。
我们计算权值为n的选手，走到第1个位置，需要的轮次run。

分类讨论：

• 当k >= run时，我们可以通过预处理，直接得出每位选手的获胜场次

• 当k < run，继续分类

  • 如果第i位选手，前面存在比他权值大的存在，那么他一场都没机会赢（Left[i] != -1）

  • 如果第i位选手，进行k轮比赛，不能轮到他，那么他一场都没赢 （k < i - 1）

  • 其他场景，统计第i位选手到达前2个位置后，还能赢多少人（Right[i] - i - 1）

详见代码。

代码

#include 
using namespace std;
#define ll long long
const int maxn = 200010;

int n, q;
int a[maxn], mp[maxn];
int num[maxn], run;
deque<int> ve;
int pos, k;
int Left[maxn];// leftest pos < i, which a[pos] > a[i]
int Right[maxn];// leftest pos > i, which a[pos] > a[i]

void init() {
	run = 0;
	while (true) {
		if (ve[0] == n) {
			break;
		}
		if (ve[0] > ve[1]) {
			swap(ve[0], ve[1]);
		}
		++run;
		++num[mp[ve[1]]];
		int tmp = ve[0];
		ve.pop_front();
		ve.push_back(tmp);
	}
	
	int pos = 0;
	for (int i = 1; i < n; ++i) {
		if (a[pos] > a[i]) {
			Left[i] = pos;
		} else {
			Right[pos] = i;
			pos = i;
		}
	}
}
int cal() {
	int res;
	if (k >= run) {// case 1
		res = num[pos];
		if (a[pos] == n) {
			res += k - run;
		}
		return res;
	}
	
	// case 2.1
	if (Left[pos] != -1) {
		return 0;
	}
	// case 2.2
	k -= pos;
	if (k < 0) {
		return 0;
	}
	return min(k, Right[pos] - pos - 1) + (pos != 0);
}
void solve() {
	scanf("%d%d", &n, &q);
	ve.clear();
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		mp[a[i]] = i;
		num[i] = 0;
		Left[i] = -1;
		Right[i] = n;
		ve.push_back(a[i]);
	}
	init();
	while (q--) {
		scanf("%d%d", &pos, &k);
		--pos;
		printf("%d\n", cal());
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}
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

最后

觉得文章不错的话， weixin gongzhonghao 关注 对方正在debug，一起快乐刷题吧~