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

快排手写,为啥超时???

Posted by master_wugui at 2011-12-01 14:02:50 on Problem 2872 and last updated at 2011-12-01 14:32:58
#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;
const int N = 51000;

int n, m = 0;
char dir[N][200];
int ind[N];                                                /* intdex of dir[] */
int num;

/* 函数 */
void Init()
{
	num = 0;
}

int Partition( int l, int r )
{
	int k = l;
	while( l < r )
	{
		while( l < r )
		{
			if( ::strcmp(dir[ ind[r] ], dir[ ind[k] ]) < 0 )              /* ind[r] <-> ind[k] */
			{   
				int temp = ind[r];
				ind[r] = ind[k];
				ind[k] = temp;
				k = r;
				break;
			}
			-- r;
		}
		while( l < r )
		{
			if( ::strcmp(dir[ ind[l] ], dir[ ind[k] ]) > 0 )              /* ind[l] <-> ind[k] */
			{
				int temp = ind[l];
				ind[l] = ind[k];
				ind[k] = temp;
				k = l;
				break;
			}
			++ l;
		}
	}
	return k;
}
void qsort( int l, int r )
{
	if( l >= r ) return;

	int k = ::Partition( l, r );
	::qsort( l, k - 1 );
	::qsort( k + 1, r );
}

bool BinSearch( int l, int r, const char* s )
{
	while( l <= r )
	{
		int mid = ( l + r ) >> 1;
		int res =  ::strcmp(dir[ ind[mid] ], s);
		if( res == 0 )
			return 1;
		else if( res > 0 )
			r = mid - 1;
		else
			l = mid + 1;
	}
	return 0;
}

void CheckSpelling()
{
	scanf( "%d", & m );
	for( int i = 1; i <= m; ++ i )
	{
		::Init();
		char wrd[105] = {0};
		scanf( "%s", wrd );
		while( ::strcmp(wrd, "-1") != 0 )                         /* check spelling for an email */
		{
			if( !::BinSearch( 0, n - 1, wrd ) )
			{
				++ num;
				if( num == 1 )
					printf( "Email %d is not spelled correctly.\n", i );
				printf( "%s\n", wrd );
			}
			scanf( "%s", wrd );
		}
		
		if( num == 0 )											  /* all correct */
		{
			printf( "Email %d is spelled correctly.\n", i );
		}
			
	}
	printf( "End of Output\n" );
}


int main()
{
	/* input directory */
	scanf( "%d", & n );
	for( int i = 0; i < n; ++ i )
	{
		scanf( "%s", dir[i] );
	}

	/* sort directory */
	for( int i = 0; i < N; ++ i )
		ind[i] = i;
	::qsort( 0, n - 1 );

	/* input email, and check spelling */
	::CheckSpelling();

	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