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

本题本人是用排序加贪心,提供一组数据,我就是在这上面wa了好几次!!!

Posted by yangzefeng at 2012-09-16 21:01:42 on Problem 2376
4 10
1 4
6 8
8 9
9 10

输出为 -1

再给一下AC代码吧,供大家参考
#include<iostream>
#include<algorithm>
#define MAX 25001
using namespace std;

struct Cow
{
	int start;
	int end;
};

int comp(struct Cow a, struct Cow b)
{
	return (a.start < b.start) || (a.start == b.start && a.end > b.end);
}

Cow cows[MAX];

int main()
{
	int nN, nT, i, temp, ret, max, flag;
	while(2 == scanf("%d%d", &nN, &nT))
	{
		ret = 0;
		for(i = 0; i < nN; i++)
			scanf("%d%d", &cows[i].start, &cows[i].end);
		sort(cows, cows+nN, comp);
		if(cows[0].start != 1)
		{
			printf("-1\n");
			continue;
		}
		temp = cows[0].end;
		if(temp == nT)
		{
			printf("1\n");
			continue;
		}
		ret++;
		i = 1;
		while(i < nN)
		{
			flag = 0;
			max = cows[i].start;
			while(cows[i].start <= temp+1)
			{
				flag = 1;
				if(max < cows[i].end)
					max = cows[i].end;
				i++;
			}
			if(flag == 0)
				break;
			ret++;
			if(max == nT)
			{
				printf("%d\n", ret);
				break;
			}
			temp = max;
		}
		if(flag == 0 || max < nT)
			printf("-1\n");
	}
	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