题解：P13887 [蓝桥杯 2023 省 Python A] 三国游戏

_fallen_leaves_ · 2025-08-28 19:34:47 · 题解

P13887 [蓝桥杯 2023 省 Python A] 三国游戏

题意

游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X, Y, Z。游戏有 n 个可能会发生的事件，每个事件最多只会发生一次，当第 i 个事件发生时会分别让 X, Y, Z 增加 A_i, B_i, C_i，游戏结束时如果有其中一个国家获胜，最多发生了多少个事件？

思路

分别考虑三家胜利的条件，优先选择一家比其他两家多的事件，然后从小到大考虑一家比其他两家少的事件，算出 3 个答案，取其中的最大值，就是此题的结果。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int x,y; 
}a[100005],b[100005],c[100005];
int n,ans=INT_MIN;
bool cmp(node x,node y)
{
    return x.x-x.y>y.x-y.y;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x;
    for(int i=1;i<=n;i++) cin>>b[i].x;
    for(int i=1;i<=n;i++) cin>>c[i].x;
    for(int i=1;i<=n;i++)
    {
        a[i].y=b[i].x+c[i].x;
        b[i].y=a[i].x+c[i].x;
        c[i].y=a[i].x+b[i].x;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    sort(c+1,c+n+1,cmp);
    int op=0,op2=0; 
    a[n+1].y=1e18;
    b[n+1].y=1e18;
    c[n+1].y=1e18;
    for(int i=1;i<=n+1;i++)
    {
        op+=a[i].x;
        op2+=a[i].y;
        if(op<=op2)
        {
            if(i==1) break;
            ans=max(ans,i-1);
            break; 
        }
    }
    op=0,op2=0; 
    for(int i=1;i<=n+1;i++)
    {
        op+=b[i].x;
        op2+=b[i].y;
        if(op<=op2)
        {
            if(i==1) break;
            ans=max(ans,i-1);
            break; 
        }
    }
    op=0,op2=0; 
    for(int i=1;i<=n+1;i++)
    {
        op+=c[i].x;
        op2+=c[i].y;
        if(op<=op2)
        {
            if(i==1) break;
            ans=max(ans,i-1);
            break; 
        }
    }
    if(ans==INT_MIN) cout<<-1;
    else cout<<ans;
    return 0;
}