题解：P14783 [NERC 2025] Battle of Arrays

Fat__Cat · 2025-12-20 18:41:17 · 题解

这是一道较为简单的博弈论题目。

分析

我们首先分析：

对于双方来说，己方回合中选择的元素 并不会因任何原因而被移除 ，所以最优策略就是选择当前己方数组中 最大的元素 。

可以利用反证法证明：

显而易见的前提：对于我方来说，对方元素越小越好 。

:::info 本段可能较为口语化，并非完全严谨的证明，仅仅作为上一段文字的补充 :::

假设存在一个元素 x ，使得当前数列的最大值 maxn_a 出动的收益小于其出动的收益。

若 maxn_a \leq maxn_b ，则出动 x 的收益将小于出动 maxn_a 的收益，因为 maxn_a 可以使 maxn_b 的量减少得更多

若 maxn_a > maxn_b ，则在最坏情况下， x \leq maxn_b ，收益显然小于 maxn_a ，在最好情况下， x > maxn_b ，收益等于 maxn_a 。

由上述过程得知， x 的收益总是小于 maxn_a ， 证毕。

存储

接下来的难点是： 如何做到在存储双方元素的同时存储双方的最大元素 。

如果暴力模拟，每次行动时间复杂度为 O(n) ，而最高时间复杂度为 O(n^2) 。考虑到本题 n , m \leq 10^5 ，显然会出现 TLE 的好成绩。

所以我们选用 STL 中的 priority_queue 存储数据。由于篇幅限制，本篇不会讲解其原理，有兴趣的读者自行参阅 OI wiki 中的描述 。

代码

~talk is cheap , show me the code .~

https://www.luogu.com.cn/record/254202167

#include<bits/stdc++.h>
using namespace std;
int n,m,T,t;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        priority_queue<int> a,b;
        for(int i=0;i<n;i++)
        {
            cin>>t;
            a.push(t);
        }
        for(int i=0;i<m;i++)
        {
            cin>>t;
            b.push(t);
        }
        while(!a.empty()&&!b.empty())
        {
            int t1,t2;
            t1=a.top(),t2=b.top();
            b.pop();
            if(t1<t2) b.push(t2-t1);
            if(a.empty()||b.empty())
            {
                if(a.empty()) cout<<"Bob\n";
                else cout<<"Alice\n";
                goto flag;
            }
            t1=b.top(),t2=a.top();
            a.pop();
            if(t1<t2) a.push(t2-t1);
            if(b.empty()||a.empty())
            {
                if(b.empty()) cout<<"Alice\n";
                else cout<<"Bob\n";
                goto flag;
            }
        }
        flag:
    }
}

这是我的第二篇题解，请多多支持！