题解 P1199 【三国游戏】

wjyyy

2018-08-05 17:09:12

Solution

**我的blog:[传送门](http://www.wjyyy.top/)** 这个题尽管题目长,主要还是证明贪心的正确性。 首先注意到,在这个题里,计算机是**贪心的**,也就是说,无论人选什么,它都会尽可能去选与人默契值最大的。想到这里可能会联想到博弈论,因为两个人的目标都是一样的。不过稍加分析会发现,人总是拿不到最优的。    因为我们选将可以看作一个配对的过程,所以在选将$i$后,第$i$行和第$i$列表格中行和列都是我们的,在自己的行和自己的列交点处就是自己的武将对了。也就是说表格是对称的。 ![](http://www.wjyyy.top/wp-content/uploads/2018/08/201808051601.png)   分析样例可以得知,最优解总是**每一行(整理后)排名第二大**中最大的那个。也就是说,每一行的最大的那一组电脑是不可能让你选到手的。一旦选择了最大的一组中的其中一个,电脑总可以先手把另一半抢掉,所以每行最大的一组是不可能选出的。而我们要证明次大中最大的那个是一定可以选到的。    当我们选择了次大中最大的那一行,电脑就毫无疑问会把那一行中最大的一个给选出来。 ![](http://www.wjyyy.top/wp-content/uploads/2018/08/201808051605.png)  此时我们把次大中最大的另一半给配上就可以了。那我们现在拿到了人所可能拿到的最大的一对武将,怎么保证计算机不拿到比自己更大的武将呢?可以看出,比当前已有的默契值更大的武将一定在其他行中处于最大的位置,(假设计算机足够聪明)如果计算机去选了那个位置,人先手去把它抢掉就行了。而计算机并没有那么聪明,它只会避免你去选能选的最大的武将,此时可以分情况讨论。 ![](http://www.wjyyy.top/wp-content/uploads/2018/08/201808051657.png) 计算机此时选择一个武将有两种影响:一是与原来的绿线相交,如果与绿线相交会直接确定一组武将,此时人是阻止不了的。但是我们可以保证现在一条线与绿线的交点值一定小于人的答案。**反证:**如果那个值比人的答案(五角星)要大而比三角形要小,那么次大中最大的就是这个值,因此这个值不可能在这个范围;而如果那个人的值比三角形还大,那次大中最大的就是三角形了。因此与绿线的交点绝不会超过五角星。    第二种影响就是不与绿线相交。对于不与绿线相交的部分,只要人去把计算机最大的抢掉,计算机就不可能抢到每一行中最大的那个。    综上所述,无论人还是计算机都无法抢到每一行中最大的那个,而根据贪心,人去选每行次大元素中最大的一定能选到,此时也能阻止计算机去选更大的元素。同时人不会输。 ## Code: ```cpp #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; } ```