我的blog：传送门

这个题尽管题目长，主要还是证明贪心的正确性。

首先注意到，在这个题里，计算机是 贪心的 ，也就是说，无论人选什么，它都会尽可能去选与人默契值最大的。想到这里可能会联想到博弈论，因为两个人的目标都是一样的。不过稍加分析会发现，人总是拿不到最优的。

因为我们选将可以看作一个配对的过程，所以在选将i后，第i行和第i列表格中行和列都是我们的，在自己的行和自己的列交点处就是自己的武将对了。也就是说表格是对称的。

分析样例可以得知，最优解总是每一行（整理后）排名第二大中最大的那个。也就是说，每一行的最大的那一组电脑是不可能让你选到手的。一旦选择了最大的一组中的其中一个，电脑总可以先手把另一半抢掉，所以每行最大的一组是不可能选出的。而我们要证明次大中最大的那个是一定可以选到的。

当我们选择了次大中最大的那一行，电脑就毫无疑问会把那一行中最大的一个给选出来。

此时我们把次大中最大的另一半给配上就可以了。那我们现在拿到了人所可能拿到的最大的一对武将，怎么保证计算机不拿到比自己更大的武将呢？可以看出，比当前已有的默契值更大的武将一定在其他行中处于最大的位置，（假设计算机足够聪明）如果计算机去选了那个位置，人先手去把它抢掉就行了。而计算机并没有那么聪明，它只会避免你去选能选的最大的武将，此时可以分情况讨论。

计算机此时选择一个武将有两种影响：一是与原来的绿线相交，如果与绿线相交会直接确定一组武将，此时人是阻止不了的。但是我们可以保证现在一条线与绿线的交点值一定小于人的答案。**反证：**如果那个值比人的答案（五角星）要大而比三角形要小，那么次大中最大的就是这个值，因此这个值不可能在这个范围；而如果那个人的值比三角形还大，那次大中最大的就是三角形了。因此与绿线的交点绝不会超过五角星。

第二种影响就是不与绿线相交。对于不与绿线相交的部分，只要人去把计算机最大的抢掉，计算机就不可能抢到每一行中最大的那个。

综上所述，无论人还是计算机都无法抢到每一行中最大的那个，而根据贪心，人去选每行次大元素中最大的一定能选到，此时也能阻止计算机去选更大的元素。同时人不会输。

Code:

#include<cstdio>
#include<algorithm>
using std::sort;
int a[510][510];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            a[j][i]=a[i][j];
        }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        sort(a[i]+1,a[i]+1+n);
        ans=ans>a[i][n-1]?ans:a[i][n-1];//选出排名第二中最大的那个
    }
    printf("1\n%d\n",ans);//一定有解
    return 0;
}