P1199 [NOIP 2010 普及组] 三国游戏 题解

· · 题解

思路

如果小涵想要获胜，就要选到默契值尽可能大的一对武将。但我们会发现，计算机选择的策略决定了小涵不可能选到这对武将，于是我们退而求其次，考虑次大值。

接着我们又发现，如果我们拿走了一个武将 a，那么计算机一定会拿走与 a 默契值最大的武将 b，这时，我们只需要拿走与 a 的默契值第二大的武将 c 就好了，此时计算机一定拿不到比小涵拿到的这对武将默契值更大的一对武将，因为默契值最大的一对武将被拆散了，而默契值第二大的一对武将在小涵的手上，故我们只需要一直用这个策略选下去，便可以让小涵手上默契值最大的一对武将的默契值始终比计算机手上默契值最大的一对武将更大，这样小涵就是必胜的。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[505][505],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>a[i][j];
            a[j][i]=a[i][j];//构造一个对称的二维表来存储武将之间的默契值
        }
    }
    for(int i=1;i<=n;i++){
        sort(a[i]+1,a[i]+1+n);//排序，求次大值
        ans=max(ans,a[i][n-1]);//更新答案
    }
    cout<<1<<"\n"<<ans;//由于小涵是必胜的，所以我们直接输出1和默契值就好
    return 0;//华丽结束
}

蒟蒻的第一篇题解，求过。