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

2376

Posted by qinpengfei121 at 2010-05-10 19:04:58 on Problem 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:
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