| ||||||||||
| 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 <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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator