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 boys at 2006-08-07 21:47:56 on Problem 2376
#include<iostream>
#include <algorithm>
using namespace std;

typedef struct node
{
	long L;
	long R;
}node;

bool cmp(node &a,node &b)
{
   if((a.L<b.L)||((a.L==b.L)&&(a.R<b.R)))return true;
   return false;
}
long i,j,k,m,a,b,n,flag,tag,num;
int counter;
int main()
{
	node n[100005];
	cin>>num>>m;
	k=0;
	tag=1;
	for(i=0; i<num;i++)
	{
		scanf("%ld%ld", &a,&b);
		n[k].L=a;
		n[k].R=b;
		if(a<=1 && b>=m) tag=0;
		k++;
	}
	counter = 0;
	if(!tag) cout<<1<<endl;
	else
	{
		flag = 0;
		sort(n,n+k,cmp);
		a=b=1;
		for(i=0; i<k; i++)
		{	
			if(n[i].L>a) break;
			else 
			{	
				while(n[i].L<=a && i<k)
				{
					if(n[i].R>b)
					b = n[i].R; 
					i++;
				}
				a=b;i--;
				counter++;
				if(b>=m) {flag=1; break;}
			}
		}
		if(!flag) cout<<-1<<endl; 
		else 
			cout<<counter<<endl;	
	}
	return 1;
}


 

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