题解：P14783 [NERC 2025] Battle of Arrays

gless_goldfish · 2025-12-20 16:00:38 · 题解

大概题意

这题题意比较复杂，我们转化一下。其实可以转化为让一个人的最大元素打另一个人的最大元素，直到某个人的元素没了为止。

可以用大根堆优先队列快速得到最大值，是一道练优先队列的好题。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        int i;
        priority_queue<int>q1,q2;
        for(i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            q1.push(x);
        }
        for(i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            q2.push(x);
        }
        while(!q1.empty()&&!q2.empty())
        {
            int x=q1.top();
            int y=q2.top(); 
            q2.pop();
            if(y-x>0)q2.push(y-x);
            if(q2.empty())break;
            x=q1.top();
            y=q2.top(); 
            q1.pop();
            if(x-y>0)q1.push(x-y);
            if(q1.empty())break;
        }
        if(q1.empty())cout<<"Bob\n";
        else cout<<"Alice\n";
    }
}