| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:有点陷阱啊,其实就是自己不小心了。带数据(后边大牛的)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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator