题干:(Uva题不给题干了)

     t组样例,每组首先给出一个M,然后给出一些线段(0 0结束),然后问怎么取能使得最少的线段覆盖区间[0, M]。

Sample Input
2
1
-1 0
-5 -3
2 5
0 0
1
-1 0
0 1
0 0
Sample Output
0
1
0 1    

解题报告:

   就是个贪心啊

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
struct Node {
	int st,ed;
	Node(){}
	Node(int st,int ed):st(st),ed(ed){}
	bool operator<(const Node & b) const{
		if(st != b.st) return st < b.st;
		return ed > b.ed;
	}
} node[MAX];
int tot,n,m,cnt,nb;
int ans[MAX];
int main()
{
	int t;
	int a,b,maxx,minn;
	cin>>t;
	while(t--) {
		tot=cnt=0;
		maxx = 0,minn = 0x3f3f3f3f;
		scanf("%d",&m);
		while(scanf("%d%d",&a,&b)) {
			if(a==0 && b==0) break;
			if(b<=0) continue;
			if(a>=m) continue;
			node[++tot] = Node(a,b);
			maxx = max(maxx,b);
			minn = min(minn,a);
		}
		sort(node+1,node+tot+1);
		int cure,curs;
		curs=cure=0;
//		if(minn >= m || maxx <= 0) {
//			puts("0");
//			if(t) puts("");
//			continue;
//		}
		int flag = 0;
		for(int i = 1; i<=tot; ) {
			if(node[i].st > curs) {
				break;	
			}
			while(i<=tot && node[i].st<=curs) {
				if(node[i].ed > cure) {
					cure = node[i].ed;
					nb = i;
				}
				i++;
			}
			//if(i!=tot) i--;
			ans[++cnt] = nb;
			curs = cure;
			if(curs >= m) {
				flag=1;break;
			}
		}
		if(flag == 0) puts("0");
		else {
			printf("%d\n",cnt);
			for(int i = 1; i<=cnt; i++) printf("%d %d\n",node[ans[i]].st,node[ans[i]].ed);
		}
		if(t) puts("");
	}
	return 0 ;
 } 

总结: 那两句读数据的时候的if去掉好像也可以AC,,反正注释掉的那一部分加上也可以AC。。