题解 CF845C 【Two TVs】

其他dalao都说是什么差分、线段树,我太菜了只能用堆。

很显然,有一种贪心的策略:能用电视1就用电视1,实在不行再用电视2。(这就好比上网课,能用电脑不用手机)

所以我们可以建立一个小根堆,以开始时间为主要关键字,用两个变量分别表示电视1和电视2的最早空闲时间,如果能用电视1就用电视1,不能用就用电视2。

作者为方便,用了 pair ,不会的用结构体也可。

#include<bits/stdc++.h>
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
#define re register
using namespace std;
priority_queue<pi,vector<pi>,greater<pi> > q;//STL大法好
int main() {
	int n,nwa=-1,nwb=-1;//时间最小是0,所以要把初值设为-1
	cin>>n;
	for(re int i=1; i<=n; i++) {
		int x,y;
		cin>>x>>y;
		q.push(mp(x,y));
	}
	while(q.size()) {
		int l=q.top().F,r=q.top().S;
		q.pop();
		if(nwa<l) nwa=r;//因为不能瞬时切换,所以不能等于
		else {
			if(nwb<l) nwb=r;
			else {
				puts("NO");//要是有一个节目看不了,那就直接输出结束
				return 0;
			}
		}
	}
	puts("YES");
	return 0;
}
原文地址:https://www.cnblogs.com/ahawzlc/p/12599539.html