问一下：我的贪心是O(n)+快排
        为什么超时？
Problem Id:2376  User Id:wpc0000 
Memory:368K  Time:1014MS
Language:G++  Result:Time Limit Exceed

Source 

//pku2376

#include <stdio.h>
#include <iostream>

//#include <fstream0>
//ifstream cin("in.txt");
//ofstream cout("out.txt");

using namespace std;

const int N0=25000;
int n,t;
int tot;

struct PII{
	long b,e;
}node[N0];

bool comp(PII a0,PII b0)
{
	if(a0.b<b0.b)return true;
	else if(a0.b>b0.b)return false;
	else return (a0.e>b0.e);
}

int QuickSort(long l,long r)
{
	long i, j, x;
	i=l;j=r;x=(l+r)/ 2;
	do{
		while (comp(node[i],node[x])) i++;
		while (comp(node[x],node[j])) j--;
		if (i <= j){
			PII temp;
			temp=node[i];node[i]=node[j];node[j]=temp;
			i++; j--;
		}
	}while( i<=j);
	if (l < j) QuickSort(l,j);
	if (i < r) QuickSort(i, r);
	return 0;
}


int init()
{
	for(int i=0;i<n;i++){
		scanf("%ld %ld\n",&node[i].b,&node[i].e);
	}
	tot=0;
	QuickSort(0,n-1);
	return 0;
}

int turn()
{
	int i,j,i0;
	tot++;
	j=0;
	long e=node[j].e;
	i=0;
	while(j<n){
		i0=j;//i=i0;
		while( (node[i].b<=node[j].e+1)&&(i<n) ){
			if(node[i].e>node[i0].e)i0=i;
			i++;
		}
		if(j!=i0)tot++;
		j=i0;
		e=node[j].e;
		if( (e>=t)||(i>=n) )break;
	}
	if( (e>=t)&&(node[0].b==1) )cout<<tot<<endl;
	else cout<<-1<<endl;
	return 0;
}

int main()
{
	while(scanf("%d %ld",&n,&t)!=EOF){
		init();	
		turn();
	}
	return 0;
}

• Re:原来sort+greedy就可以ac - -# (12) Dreamquster 2007-02-07 12:14:27