题解：P14783 [NERC 2025] Battle of Arrays

Dustlpes_CZY · 2025-12-20 09:53:39 · 题解

题目大意

选取一个元素 x，并从对手的数组中选取最大的元素 y，两人 PK 。

• 如果 x 打得过 y，使 y 从对手数组移除（x \ge y）。
• 反之 y 减少 x（x \le y）。

思路

考虑贪心：选择的 x 是最小值还是最大值好呢？

毫无疑问：最大值。使（最好情况）y 被移除。

• 如果你可以让 y 从对手数组中移除，那一定要让 y 移除（因为一个人跟你打和两个人跟你打是完全不同的结果）。
• 如果你不可以让 y 从对手数组中移除（即你打不过对手，但你有援兵），那你就消耗对手，即使 y 变为 y - x，等待援兵，（即等下一次 PK）。

代码逻辑

使用 priority_queue 获得最大值，f 表示谁赢了，a 表示我们的视角，b 表示对手，使用 swap 转换双方视角。

理论存在，实践开始！

AC CODE

#include <bits/stdc++.h>
#define LL long long
#define the return
#define prity priority_queue
#define lop(x,a,b,c) for(LL x=a; b-x+c; x+=c)
using namespace std;
const LL N=1e5+5;
LL n,k,m;
inline LL in(){ LL x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }
    while(c>='0'&&c<='9'){ x=x*10+(c-'0'); c=getchar(); } the x*f;
}//快读 
int main(){
    LL T=in();
    while(T--){
        n=in(),m=in();
        prity<LL> a,b;//prity 每次返回最大值 
        lop(i,1,n,1) a.push(in());//Alice
        lop(i,1,m,1) b.push(in());//Bob
        bool f=0;//Bob win,a.size==0
        while(a.size() && b.size()){//判空 
            LL x=a.top(),y=b.top();
            //这里使 a PK b 
            b.pop();// x >= y
            if(x < y) b.push(y-x);//打不过,消耗 
            f^=1;//赢家转换 1-->Alice,0-->Bob
            swap(a,b);//转换视角 
        }
        cout<<(f?"Alice":"Bob")<<"\n";
    }
    the 0;
}

写在最后： 这是本人的第三篇题解！！！赏个赞再走吧！ （管理员大大辛苦了！）