Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大家注意特判

Posted by Kamisama_lry at 2015-07-03 20:15:11 on Problem 2376
这个题的代码很好写,排序然后贪心就好了。但是有一些特判需要注意。
如果n=1,如数据:1 5 1 5   就需要加一条特判直接输出 1  如果跑贪心就跪了。
其次排序结果如果第一个段开头不是1,可以直接输出 -1。
附个人代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 25100;
struct Segment{
	int l, r;
}segment[MAXN];
int n, t, tail, time, MAX;
int cmp(Segment a, Segment b){ return a.l < b.l || a.l == b.l && a.r > b.r;}
int main(){
	memset(segment, 0, sizeof(segment));
	scanf("%d%d", &n, &t);
	for(int i = 1; i <= n; i++) scanf("%d%d", &segment[i].l, &segment[i].r);
	sort(segment + 1, segment + n + 1, cmp);
	tail = segment[1].r, time++;
	if(segment[1].l != 1) { printf("-1"); return 0;}
	if(segment[1].l == 1 && segment[1].r == t) { printf("1"); return 0;}
	for(int i = 1; i <= n; i++){
		if(segment[i].l <= tail + 1) MAX = max(MAX, segment[i].r);
		else{
			if(tail == MAX) { printf("-1"); return 0;}
			tail = MAX, i--, time++;
		}
		if(MAX == t) { tail = MAX; time++; break;}
	}
	if(tail != t) { printf("-1"); return 0;}
	printf("%d", time);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator