P1199 三国游戏 题解
这道题要求最后得到的两方的默契值最大的武将,
小涵的默契值大于计算机,
首先,我们这个解法获胜的思路是,每个武将对应的所有配对值中最大的值,已经被拆散
在这种情况下,场上存在的只剩所有的“次大值”,就是我们拿来排序的那一堆
这时候小涵拿到了“次大值”中的最大值,肯定是场上最高的分数
策略就是:
先考虑最开始的情况:
1.从武将中找出武将i,记下与i的默契值第二大的武将j,使得i与j的默契值最大
2.小涵选出i,那么计算机只会选出与i默契值最大的武将p
此时与p的默契值最大值一定是i。为什么呢?
假设与p的默契值最大值是k,次大值是k2,第某大的值是i
那么p-k > p-k2 > p-i
这里的'-'是对应的意思
而i-p > i-j
所以p-k2 > i-j
也就是与p默契值第二大的值大于与i默契值第二大的值
显然小涵开始时应该改选p,矛盾。
因此,我们第一次选了i,取得了次大值中的最大值,同时拆掉了i的最大值和p的最大值
3.小涵选出l(i的默契值次大值),计算机选m,m是:i,或,l除了与i外,的最大值
可能有两种原因:一是l-m是l除了与i外的最大值,拆了最大值正合我意
二是i-m比l除了与i外的最大值更大(但是不会比i-l大,
因为i的最大值已经拆掉了,次大值就是i-l),即i-l > i-m > (l除了与i外的最大值)
这时候l的最大值拆不拆都是无所谓的,反正小于我们的i-l
然后小涵选了n拆了m的最大值m-n
计算机接着拆最大值,要么是n的最大值,要么比i-l小,证法同上
两个人就这么拆最大值,就把最大值拆完了,剩下的就是次大值,我们的i-l就是次大值中最大的
所以还是不要想着证明了,编程拿搜索对拍验证吧,
找了几十个证明也没看到严谨的,实在是难想。。。
code:
#include<cstdio> #include<algorithm> int n; int a[510][510]; int main() { int i,j,maxans=-1; scanf("%d",&n); for(i=1;i<n;i++) { a[i][i]=-1; for(j=i+1;j<=n;j++) { scanf("%d",&a[i][j]); a[j][i]=a[i][j]; } } a[n][n]=-1; for(i=1;i<=n;i++) std::sort(a[i]+1,a[i]+n+1); for(i=1;i<=n;i++) if(a[i][n-1]>maxans) maxans=a[i][n-1]; printf("1\n%d\n",maxans); return 0; }
上一篇: 终于开始发力后置双摄 索尼XA3 Ultra手机现身
下一篇: Spring的jdbcTemplate 与原始jdbc 整合c3p0的DBUtils 及Hibernate 对比 Spring配置文件生成约束的菜单方法
推荐阅读
-
管宁凭什么在三国中首屈一指?他的游戏,很少人懂!
-
【题解】 洛谷 P2649 游戏预言
-
游戏优化大师能优化哪些游戏?游戏优化大师常见问题解答分享
-
笔试编程题 数字游戏 Java题解 牛牛举办了一场数字游戏,有n个玩家参加这个游戏,游戏开始每个玩家选定一个数,然后将这个数写在纸上(十进制数,无前缀零),然后接下来对于每一个数字将其数位按照非递减
-
P1199 三国游戏 题解
-
八皇后问题解法大全及编写八皇后小游戏
-
[洛谷题解]P1000 超级玛丽游戏 「v1.0」
-
win11玩游戏闪退怎么办 win11系统游戏闪退问题解决方法
-
NVIDIA发布GeForce 430.64驱动 优化《全战:三国》等游戏
-
javascript游戏开发之《三国志曹操传》零部件开发(一)让静态人物动起来_javascript技巧