【题目链接】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\log n)O(nlogn)的虽然可以通过问题但不是效率最高的做法。以下提供两种O ( n ) O(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维护最大值、次大值变量#includebits/stdc.husingnamespacestd;constintN505;intn,g[N][N],ans;intmain(){cinn;for(inti1;in;i)for(intji1;jn;j){cing[i][j];g[j][i]g[i][j];//构成完整的对称邻接矩阵}for(inti1;in;i){intmaxVal10,maxVal20;for(intj1;jn;j){if(g[i][j]maxVal1){maxVal2maxVal1;maxVal1g[i][j];}elseif(g[i][j]maxVal2)maxVal2g[i][j];ansmax(ans,maxVal2);}}cout1endlans;return0;}解法2使用链表#includebits/stdc.husingnamespacestd;constintN505;intn,g[N][N],ans;intmain(){cinn;for(inti1;in;i)for(intji1;jn;j){cing[i][j];g[j][i]g[i][j];//构成完整的对称邻接矩阵}for(inti1;in;i){listintlis{0,0};//lis.front()最大值 lis.back()次大值for(intj1;jn;j){if(g[i][j]lis.front()){lis.push_front(g[i][j]);lis.pop_back();}elseif(g[i][j]lis.back()){lis.pop_back();lis.push_back(g[i][j]);}ansmax(ans,lis.back());}}cout1endlans;return0;}