题目描述

有一个 \(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;
}