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

Re:有点陷阱啊,其实就是自己不小心了。带数据(后边大牛的)

Posted by 785815369 at 2010-05-03 21:33:01 on Problem 2376
In Reply To:有点陷阱啊,其实就是自己不小心了。带数据(后边大牛的) Posted by:dynamic_study at 2009-08-21 10:47:46
看了这句话就AC了 拿那位大牛的话说,前边那头傻牛是1--3;
后边那头蛮牛就可以是4----6,不必是由3开始。
我的代码

#include<iostream>
using namespace std;
struct NODE{
	int x;
	int y;
};
int compare(const void *p1,const void *p2){
	if(((NODE *)p1)->x==((NODE *)p2)->x)
		return ((NODE *)p2)->y-((NODE *)p1)->y;
	return ((NODE *)p1)->x-((NODE *)p2)->x;
}
int count(NODE node[],int n,int t){
	qsort(node,n,sizeof(node[0]),compare);
	int i=0,total,max;
	if(node[i].x!=1)return -1;
	total=1;
	max=node[i].y;
	while(node[i].y<t&&i<n){
		int j=i+1;
		while(node[j].y<=node[i].y&&j<n)j++;
		if(j>=n||(j<n&&(node[j].x-1)>node[i].y))return -1;
		total++;
		max=node[j].y;
		if(node[j].y>=t)return total;
		for(int m=j+1;m<n;m++){
			if((node[m].x-1)<=node[i].y&&node[m].y>max){
				j=m;
				max=node[m].y;
			}
			else if(node[m].x>node[i].y)break;
		}
		i=j;
	}
	if(i>=n)return -1;
	return total;
}
int main(){
	int n,t;
	while(scanf("%d%d",&n,&t)!=EOF){
		NODE node[25002];
		for(int i=0;i<n;i++){
			scanf("%d%d",&node[i].x,&node[i].y);
		}
		int k=count(node,n,t);
		printf("%d\n",k);
	}
}

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