P2207 Photo B 题解

每两只奶牛的关系可以视为一个区间，等于说我们需要尽可能少地在

[1,n]

上的整点取点，确保每个区间里都有一个点

而众所周知，存在许多相交的区间，如果我们尽可能把点放在交集中的话，那就好了

而后我就想出了一个方法

我们持续性地对较为靠近的两个区间作交集运算，直到眼下这个集不再和任何一个附近的区间成交集，那么只要在这个小的交集中放一个点，就能确保这个交集的所有母集中都能至少有一个点

相当于是每次两两合并一个区间

为了确保运算效率最高，我们考虑贪心，把区间从小到大排一遍，按照左端点或右端点排序都无所谓

每次只要眼下的交集不能和任何一个剩余的区间作交集时，就让答案加一

最后再将答案加一即可

需要注意的是输入数据不确保

a<b

所以必须输入时就比较预处理

CPP

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int n,k; 
struct line{
	int l,r;
}sorted[1005];
bool cmp(line a, line b){
	if(a.r > b.r)return true;
	return false;
}
stack<line> cows;
int main(){
	cin >> n >> k;
	for(int i=0;i<k;i++){
		int left,right;
		cin >> left >> right;
		sorted[i].l = min(left,right);
		sorted[i].r = max(left,right);
	}
	sort(sorted,sorted+k,cmp);
	for(int i=0;i<k;i++)cows.push(sorted[i]);
	int ans = 0;
	while(!cows.empty()){
		line top1 = cows.top();
		cows.pop();
		if(cows.empty()){
			ans++;
			break;
		}
		line top2 = cows.top();
		cows.pop();
		if(top1.r > top2.l){
			line tmp;
			tmp.l = top2.l;
			tmp.r = top1.r;
			cows.push(tmp);
		}
		else{
			ans++;
			cows.push(top2);
		}
	}
	cout << ans+1 << endl;
	return 0;
}

文章操作

相关推荐

评论

P2207 Photo B 题解