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 mgyrider at 2014-06-21 18:12:11 on Problem 2376
#include<stdio.h>
#include<algorithm>
#define M 25005

using namespace std;

int N,T;
struct node
{
	int x;
	int y;
}A[M];

bool cmp(node a,node b)
{
	if(a.x != b.x)
	return a.x < b.x;
	else
	return a.y > b.y;
}

int main()
{
	int i,j,str,end;
	int ans,end2;
	while(~scanf("%d%d",&N,&T))
	{
		for(i=0;i<N;i++)
		scanf("%d%d",&A[i].x,&A[i].y);
		sort(A,A+N,cmp);
		if(A[0].x != 1)
		{
			printf("-1\n");
			continue;
		}
		ans = 1;
		end2 = 0;
		end = A[0].y;
		for(i=1;i<N;i++)
		{
			if(A[i].x > end+1)
			{
				
				end = end2;
				ans++;
			}
			if(A[i].x <= end+1 && A[i].y >= end+1)
			{
				if(A[i].y > end2)
				end2 = A[i].y;
				if(A[i].y == T)
				{
					end = T;
					ans++;
					break;
				}
			}
			
		}
		if(end != T)
		printf("-1");
		else
		printf("%d\n",ans);
		
	}
}

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