SCOI 2010 连续攻击游戏

solution

直接就硬刚

我愿称贪心为暴力

因为题目中要求一定从小到大贪心，那么当前点的下标有能够选取的较大点,那么它一定可以和前面的一个较小点连接，所以可以直接选取这个点

若你选的当前点是较小点，那么就需要考虑后面的怎么往上接才能使得答案最优。感性理解一下，答案应该在较大点密集的地方，然后往后找到较大点等于后面的较小点，然后就像当于接住了（就那个感觉，能明白吗），连起来之后形成的最长的链的长度就是最优的答案了

为了避免爆掉数组，我们采用的vector，自动申请空间存储，i从1往后遍历尝试找可行方案，找不到就退出。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

// #define int long long

using namespace std;

inline int read(){

	int x = 0,w = 1;

	char ch = getchar();

	for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;

	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';

	return x * w;

}

const int maxn = 100010;

vector<int> G[maxn];

int cnt[maxn];

int main(){

	int n = read();

	for(int i = 1; i <= n ;i++){

		int u = read(), v = read();

		if(u > v) swap(u, v);

		cnt[v]++;

		G[u].push_back(v);

	}

	int ans = n;

	for(int i = 1; i <= n; i++){

		if(cnt[i]){

			cnt[i]--;

			continue;

		}

		if(!G[i].size()){

			ans = i - 1;

			break;

		}

		int tmp = G[i][0];

		for(int j = 1; j < G[i].size(); j++){

			if(cnt[G[i][j]] > cnt[tmp] || (cnt[G[i][j]] == cnt[tmp] && G[i][j] > tmp))

				tmp = G[i][j];

		}

		cnt[tmp]--;

	}

	cout << ans << '\n';

	return 0;

}

巴特西

SCOI 2010 连续攻击游戏(贪心，图论)

SCOI 2010 连续攻击游戏

solution

最新文章

热门文章