题意理解

废话不多说，我们先看题目。有N个武将（N为偶数且N>4），每一对武将有一个不重复的默契值。~~网瘾少年~~小涵与计算机对战，小涵先手，计算器会尽己所能不让小涵拿到小涵目前可以组出的最大默契值。求小涵是否能胜，以及获胜情况下能够拿到最大的默契值。

提取关键信息
N>4且N为偶数
每一对武将的默契值不重复
计算机会一直拆小涵能选的最大默契值

思路分析

接下来我们分析一下思路。

N>4，意味着小涵与机器人都至少能够选到3个武将；
默契值不重复，意味着不会出现平局；
而计算机的策略，则意味着小涵每一轮能够得到的最大默契值其实是当前状态下他能够选到的次大默契值

根据 3 可以得出，当小涵选出一个武将时，该武将所能收获的最大默契值双方都不可能得到，因此，只要确保每个剩余武将的次大默契值均小于小涵第一次所选的武将的次大默契值，那么小涵便是必胜的。因此如果小涵第一次选择所有武将中次大默契值最大的武将，并在前三轮选择中把次大默契值拿下，便可以必胜。

进一步说，所有武将中最大的次大默契值，就是答案。这里提供一下简单的证明。

证明
1：小涵必胜
当小涵选择次大默契值最大的武将时，计算机会拆掉该武将所对应的最大默契值。因为我们选择的是次大默契值最大的武士，所以该武士所对应的最大默契值同时也是最大默契值对应武士的最大默契值。因此在我们选择次大默契值后，计算机在一步之内无论如何都不可能超过我们所选的默契值。
那么，一步之外呢？
一步之外的威胁来自于其他武将的最大默契值。因为我们选的是次大默契值最大，所以可能有武将的最大默契值大于我们的次大默契值。但是，通过上述证明可得，剩下的最大默契值一定不在已选的三个武将之内。所以，计算机如果想要得到那个最大默契值，一定需要再选两个武将。那么，这样的话……我们就可以以彼之道还施彼身——使用与计算机相同的策略一直拆掉计算机的最大值就可以确保我们的默契值是最大的了。哈哈哈没想到计算机你还有今天！
2：最大的次大默契值就是答案
根据之前的证明，我们所能拿到的一定是目前所有可选默契值中次大的默契值，那最大的次大默契值就是我们能拿到的最大的默契值了。

证毕。

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int a[510][510];
int main()
{
	int n,ans=0,max1=0,max2=0;
	cin>>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];    //数据是一个三角形，我们将它手动转换为矩阵
		}
	}
	for(int i=1;i<=n;++i)
	{
		max1=0,max2=0;
		for(int j=1;j<=n;++j)
		{
			if(a[j][i]>max1)
			{
				max2=max1;
				max1=a[j][i];
			}
			else if(a[j][i]>max2)
			{
				max2=a[j][i];
			}
		}
		ans=max(ans,max2);
	}    //手动找最大的次大默契值，可用for+sort替换。
	printf("1\n%d\n",ans);
	return 0;
}

原文链接：https://blog.csdn.net/weixin_67719802/article/details/124080418