| ||||||||||
| 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 | |||||||||
我用的排序加贪心,各位看下有什么数据过不了,帮忙改下,谢谢指点。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator