[NOIP2010 普及组] 三国游戏

本文主要是介绍[NOIP2010 普及组] 三国游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

引

为了夯实基础

解法

考虑严谨证明一下最优策略
首先当小涵选了一个数后，一定会产生一个最优搭配和一个次优搭配，
明显最优搭配永远取不到，那么他就只能选次优搭配
还有一个选择是在选一个不相干的数，产生新的最优搭配，但是无济于事
所以最后一定是取最大的次优搭配

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
using ll = long long ;
using namespace std;
const int N=2e5+7,M=1e6;
const ll mod=998244353,LLF=1e18;int n;int main(){scanf("%d",&n);vector<vector<int> > a(n+1);int ans=0;for(int i=1;i<n;i++) {for(int j=i+1;j<=n;j++) {int x; scanf("%d",&x);a[i].push_back(x);a[j].push_back(x);}}for(int i=1;i<=n;i++) {sort(a[i].begin(),a[i].end(),greater<int>());ans=max(ans,a[i][1]);}printf("1\n%d",ans);
}

结

这算不算水博客呀

这篇关于[NOIP2010 普及组] 三国游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---