【刷题】【博弈论】三国游戏

（luogu）

首先，我们这个解法获胜的思路是，每个武将对应的所有配对值中最大的值，已经被拆散

在这种情况下，场上存在的只剩所有的“次大值”，就是我们拿来排序的那一堆

这时候小涵拿到了“次大值”中的最大值，肯定是场上最高的分数

为什么呢？用反证法

按照小涵的选法，小涵第一次选了武将i，其中i对应的最大值是j，次大值是l，即i-j > i-l

这里的'-'是对应的意思

这时候，计算机一定会选择j

如果j对应的所有配对值中，最大值也是i，那么i和j这两个点的对应最大值都被拆散了

是不是j对应的最大值一定是i呢？是的

假设j对应的最大值是k，i是j对应的次大值，即j-k > j-i

那么就有j-k > j-i > i-l，这时候我们肯定会选择j作为第一个武将

因为j-i（j的对应次大值）大于i-l（i的对应次大值），与选法矛盾

也就是说，我们第一次选了i，取得了次大值中的最大值，同时拆掉了i的最大值和j的最大值

接下来小涵选了l，然后计算机选了另一个武将m

计算机选m有两种原因：一是l-m是l的最大值，拆了最大值正合我意

一是i-m比l的最大值更大（但是不会比i-l大），即i-l > i-m > l的最大值

这时候l的最大值拆不拆都是无所谓的，反正小于我们的i-l

然后小涵选了n拆了m的最大值m-n

计算机接着拆最大值，要么是n的最大值，要么比i-l小，证法同上

两个人就这么拆最大值，就把最大值拆完了，剩下的就是次大值，我们的i-l就是次大值中最大的

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n;
int d[503][503];
int ans,mx1,mx2;

int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            scanf("%d",&d[i][j]);
            d[j][i]=d[i][j];
        }

        mx1=mx2=0;
        for(int j=1;j<=n;j++)
        {
            if(d[i][j]>mx1)
                mx2=mx1,mx1=d[i][j];
            else if(d[i][j]>mx2)
                mx2=d[i][j];
        }
        ans=max(ans,mx2);
    }
    printf("%d\n%d\n",1,ans);
    return 0;
}