luogu P1199 【三国游戏】

首先很明显这是一道贪心题。

贪心方法很多dalao已经写出来了，找每个武将次大值最大的武将。

呢么我们定义一个数组\(f[N][2]\) ， 其中\(f[i][0]\)用来储存第\(i\)个武将的次大值、\(f[i][1]\)来存储第\(i\)个武将的最大值。

呢么对于第\(i\)行第\(j\)列我们读进来的武力值\(x\)既是第\(i\)个武将的武力值，又是第\(i+j\)个武将的武力值。

呢么就可以

if(x > f[i][1]) f[i][0] = f[i][1],f[i][1] = x;//如果x大于最大值，呢么当前的最大值就是该武将的次大值。 else if(x > f[i][0]) f[i][0] = x;//如果x只大于次大值，呢么x就是新的次大值

通过这个方法我们就可以避免排序这个复杂又耗时的过程

AC coding

#include <bits/stdc++.h> using namespace std;const int N = 505; int n,maxx = 0,f[N][2] = {};inline int read() {register int x = 0;register char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9'){x = (x<<3)+(x<<1) + ch-'0';ch = getchar();}return x; }int main() {n = read();for(register int i = 1;i <= n;i++){for(register int j = 1;j <= n-i;j++){register int x = read();if(x > f[i][1]) f[i][0] = f[i][1],f[i][1] = x;else if(x > f[i][0]) f[i][0] = x;if(x > f[i+j][1]) f[i+j][0] = f[i+j][1],f[i+j][1] = x;else if(x > f[i+j][0]) f[i+j][0] = x;}}for(register int i = 1;i <= n;i++) maxx = max(maxx,f[i][0]);printf("1\n%d\n",maxx);return 0; }

转载于:https://www.cnblogs.com/Mark-X/p/11404653.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的luogu P1199 【三国游戏】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。