【题目链接】

ybt 1952：【10NOIP普及组】三国游戏
洛谷 P1199 [NOIP 2010 普及组] 三国游戏

【题目难度】：C

【题目考点】

1. 贪心

2. 博弈论

3. 图论

【解题思路】

看到题目给的表格，很容易能想到这是表示无向图的邻接矩阵。因此可以在图论模型下理解该题。
每个武将是一个顶点，任何两个顶点之间都有无向边，该图是完全图。设武将x、y的默契值为顶点x到顶点y的边权，记为g[x][y]。
玩家与电脑轮流选择顶点，当所有顶点选择结束后，问哪一方选择出的顶点之间的最大边权是更大的。

与顶点a相连的边中，顶点a到顶点x的边的边权是最大的，顶点a到顶点y的边的边权是第二大的。即在邻接矩阵g的第a行中，g[a][x]是最大值，g[a][y]是非严格次大值，满足g[a][x] >= g[a][y]。
假设玩家选了顶点a，那么按照题目描述，电脑的策略是选择与顶点a相连边权最大的边所连的顶点x。这样玩家和电脑都无法选择到与顶点a相连的边权最大的边。
那么玩家下一步可以选择顶点y，也就是可以得到与顶点a相连的边权第二大的边。

对于任意顶点，该规律都成立：玩家是先手的，玩家和电脑都无法获得与每个顶点相连的边权最大的边，而玩家可以选择获得与每个顶点相连的边权次大的边。

玩家就可以比较与每个顶点相连的边权次大的边，看哪条边权值最大，就选择哪条边。
双方都在无法获得与每个顶点相连的边权最大的边的前提下，玩家所选择的边就是剩下的可能选出的边中边权最大的边，因此玩家会赢得游戏。

因此玩家有必胜策略，首先输出1。
而后求出与每个顶点相连的边权第二大的边，也就是邻接矩阵每一行的非严格次大值。求这些边边权的最大值，即为本题结果。

维护次大值的方法：如果先排序再取第1、2个元素，或使用堆，都是$O(n\log n)$的，虽然可以通过问题，但不是效率最高的做法。

以下提供两种$O(n)$时间复杂度求序列最大值及次大值的方法：

方法1：维护最大值、次大值变量

正确做法是维护两个变量：maxVal1保存最大值，maxVal2保存次大值。

• 如果当前关注的值v大于等于最大值maxVal1，那么次大值设为maxVal1，最大值设为v
• 否则，如果当前关注的值v，小于最大值maxVal1同时大于maxVal2，那么将次大值设为v。

方法2：使用链表

链表只保存两个元素，头部元素f表示最大值，尾部元素b表示次大值。

• 如果当前关注的值v大于等于最大值f，那么将v头插入链表，删除尾部元素。而后表示最大值的头部元素值为v，表示最小值的尾部元素值为f。
• 否则，如果当前关注的值v，小于头部元素f同时大于尾部元素b，那么删除尾部元素，将v尾插进链表。而后表示最大值的头部元素值为f，表示最小值的尾部元素值为v。

【题解代码】

解法1：维护最大值、次大值变量

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, g[N][N], ans;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
		for(int j = i+1; j <= n; ++j)
		{
			cin >> g[i][j];
			g[j][i] = g[i][j];//构成完整的对称邻接矩阵 
		}
	for(int i = 1; i <= n; ++i)
	{
		int maxVal1 = 0, maxVal2 = 0;
		for(int j = 1; j <= n; ++j)
		{
			if(g[i][j] >= maxVal1)
			{
				maxVal2 = maxVal1;
				maxVal1 = g[i][j];
			}
			else if(g[i][j] > maxVal2)
				maxVal2 = g[i][j];
			ans = max(ans, maxVal2);
		}
	}
	cout << 1 << endl << ans; 
	return 0;
}

解法2：使用链表

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, g[N][N], ans;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
		for(int j = i+1; j <= n; ++j)
		{
			cin >> g[i][j];
			g[j][i] = g[i][j];//构成完整的对称邻接矩阵 
		}
	for(int i = 1; i <= n; ++i)
	{
		list<int> lis{0,0};//lis.front()：最大值 lis.back()：次大值 
		for(int j = 1; j <= n; ++j)
		{
			if(g[i][j] >= lis.front())
			{
				lis.push_front(g[i][j]);
				lis.pop_back();
			}
			else if(g[i][j] > lis.back())
			{
				lis.pop_back();
				lis.push_back(g[i][j]);
			}
			ans = max(ans, lis.back());
		}
	}
	cout << 1 << endl << ans; 
	return 0;
}