题解：CF2107B Apples in Boxes

wwwidk1234 · 2025-05-07 19:39:14 · 题解

题目

有 n 个盒子，其中 i 第一个盒子里装着 a_i 个苹果。汤姆和杰瑞轮流捡苹果，他们需要轮流选择一个装有苹果的盒子 i，并从该盒子中拿走 1 个苹果。

胜负规则：

• 如果不存在有效的盒子，那么当前玩家判负。
• 如果在拿完苹果之后 a 的最大值与最小值之差 >k，那么当前玩家判负。

汤姆和杰瑞都绝顶聪明，如果他们都以最佳策略操作，求出赢家。

思路

记 a_{\max},a_{\max^\prime},a_{\min} 分别表示 a 数组中最大、次大、最小的元素。

可以发现，如果第一步无论怎么操作都会导致 a_{\max}-a_{\min}>k，那么直接判汤姆失败，否则每一次操作均在 a_{\max} 盒子拿走一个苹果可以保证 a_{\max}-a_{\min} \le k，因为后续的操作只会使 a_{\max}-a_{\min} 比原来的值更小。

在进行 \sum a_i 步操作之后可以把所有苹果全部拿走，拿走最后一个苹果的玩家将获胜（因为下一步没法操作，将被判负）。

综上所述，

• 当 \max \left\{ a_{\max}-1,a_{\max^\prime} \right\} - a_{\min} > k 时，汤姆第一步无论如何操作都会失败，那么胜者为杰瑞；
• 否则，当 \sum a_i 为奇数时，汤姆获胜，否则杰瑞获胜。

代码

Submission #318717187.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int a[N],n,k;
inline bool solve()
{
    cin>>n>>k;
    ll mx1=0,mx2=0,mn=1.2e18;
    ll s=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>mx1) mx1=a[i];
        else if(a[i]>mx2) mx2=a[i];
        if(a[i]<mn) mn=a[i];
        s=(s+a[i])%2;
    }
    mx1--;
    // cerr<<mx1<<' '<<mx2<<' '<<mn<<endl;
    if((max(mx1,mx2)-mn)>k) return 0;  //开幕雷击情况 
    if(s%2==1) return 1;
    else return 0;
}
int main()
{
//  freopen("neuvillette.in","r",stdin);
//  freopen("neuvillette.out","w",stdout);
    int T;
    cin>>T;
    while(T--) puts(solve()?"Tom":"Jerry"); 
    return 0;
}
/*
操作直到数组为[0,0,0,...]的次数:sigma(a) 
*/