GYM 105322 B
题目描述
有一个 \(N\) 个数的序列 \(A\)，两个人将轮流进行以下操作之一：
- 删除序列中其中一个最小值。
- 在所有数 \(>0\) 的情况下，你可以令所有元素减一。
求最终哪一方会赢。
思路
假设现在只有两个数，那么只要有一方删掉了较小值，那么另一方就赢了，所以两方一定会不断减一知道实在不能减为止。
现在我们将 \(A\) 排序。
在到达只有两个数的局面之前，一定会先删掉 \(N-2\) 个元素，而这里减法是将整个数组减一，所以我们不关心其顺序，总共会减 \(A_{N-1}\) 次。
只需判断次数的奇偶性即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000001;
int n;
ll a[MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
if((a[n - 1] + n - 1) % 2 == 0) {
cout << "Eric";
}else {
cout << "Cire";
}
return 0;
}