| ||||||||||
| 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 | |||||||||
2376为什么会TLE呢,o(n)的算法难道不行么??????????
求助!!!!!!!!!!!!!
求助!!!!!!!!!!!!!
求助!!!!!!!!!!!!!
//TLE code:
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct node
{
int x;
int y;
};
node cnt[25010];
int N,E;
bool cmp(node a,node b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int main()
{
while (scanf("%d %d",&N,&E) != EOF)
{
int minn = 100000000;
int maxn = 0;
for (int i = 0; i < N; ++i)
{
scanf("%d %d",&cnt[i].x,&cnt[i].y);
minn = min(minn,cnt[i].x);
maxn = max(maxn,cnt[i].y);
}
if (minn > 1 || maxn < E)
printf("-1\n");
else
{
sort(cnt,cnt + N,cmp);
if (cnt[0].x != 1)
{
printf("-1\n");
}
if (cnt[0].y >= E)
{
printf("1\n");
}
int i = 1;
int s = cnt[0].x;
int e = cnt[0].y;
int sum = 1;
for (; i < N; ++i)
{
//cout << i << " " << s << " " << e << endl;
if (e >= E) break;
if (s == cnt[i].x) { e = cnt[i].y; continue; }
if (cnt[i].x >= s && cnt[i].x <= e)
{
if (cnt[i].y >= E)
{
s = cnt[i].x;
e = cnt[i].y;
sum++;
break;
}
else continue;
}
else
{
if (e + 1 == cnt[i].x) { s = cnt[i].x; e = cnt[i].y ; }
else { s = cnt[i - 1].x; e = cnt[i - 1].y; i -= 1; };
sum++;
}
}
//cout << s << " " << E << endl;
if (e >= E) printf("%d\n",sum);
else printf("-1\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator