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

再贴一次代码250MS,程序主要受限于I/O,目前发现fgets()比scanf,getchar,gets等都要快

Posted by CLANNAD_WAWA at 2014-05-30 22:58:38 on Problem 1002
#include <stdio.h>
#include <stdlib.h>

void Max_Heapify (int source[], int i, int size)
{
	int left = i * 2 + 1;
	int right = i * 2 + 2;
	int largest;
	if (left <= size - 1 && source[left] > source[i])
	{
		largest = left;
	}
	else
	{
		largest = i;
	}
	if (right <= size - 1 && source[right] > source[largest])
	{
		largest = right;
	}
	if (largest != i)
	{
		int temp;
		temp = source[i];
		source[i] = source[largest];
		source[largest] = temp;
		Max_Heapify (source, largest, size);
	}
}

void Max_Heap (int source[], int size)
{
	int i;
	for (i = (size - 1) / 2; i >= 0; --i)
	{
		Max_Heapify (source, i, size);
	}
}

void HeapSort (int source[], int size)
{
	int temp;
	int i;
	Max_Heap (source, size);
	for (i = size - 1; i >= 1; --i)
	{
		temp = source[i];
		source[i] = source[0];
		source[0] = temp;
		--size;
		Max_Heapify (source, 0, size);
	}
}

int main (int argc, char * argv[])
{
	int n;
	char TelTemp[50];
	int TelTable[100000];
	int i;
	int j;

	char symbol_table[100];

	int Frequency = 1;	
	int have_result = 0;
	
	symbol_table['0'] = 0;
	symbol_table['1'] = 1;
	symbol_table['A'] = symbol_table['B'] = symbol_table['C'] = symbol_table['2'] = 2;
	symbol_table['D'] = symbol_table['E'] = symbol_table['F'] = symbol_table['3'] = 3;
	symbol_table['G'] = symbol_table['H'] = symbol_table['I'] = symbol_table['4'] = 4;
	symbol_table['J'] = symbol_table['K'] = symbol_table['L'] = symbol_table['5'] = 5;
	symbol_table['M'] = symbol_table['N'] = symbol_table['O'] = symbol_table['6'] = 6;
	symbol_table['P'] = symbol_table['R'] = symbol_table['S'] = symbol_table['7'] = 7;
	symbol_table['T'] = symbol_table['U'] = symbol_table['V'] = symbol_table['8'] = 8;
	symbol_table['W'] = symbol_table['X'] = symbol_table['Y'] = symbol_table['9'] = 9;
	
	scanf ("%d", &n);
	getchar();

	for (i = 0; i < n; ++i)
	{		
		int times = 6;	
		TelTable[i] = 0;
		//scanf ("%s", TelTemp);
		//gets (TelTemp);	
		
		fgets (TelTemp, 50, stdin);

		for (j = 0; j < 50; ++j)
		{	
			if (TelTemp[j] != '-')
			{				
				TelTable[i] = TelTable[i] * 10 + symbol_table[TelTemp[j]];
				--times;
				if (times < 0)
				{
					break;
				}
			}		
		}
	}
	

	HeapSort (TelTable, n);

	for (i = 0; i < n - 1; ++i)
	{
		if (TelTable[i] == TelTable[i + 1])
		{
			++Frequency;
		}
		else
		{
			if (Frequency >= 2)
			{
				printf ("%03ld-%04ld %d\n", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
				Frequency = 1;
				have_result = 1;
			}
		}
	}
	if (Frequency >= 2)
	{
		printf ("%03ld-%04ld %d\n", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
		Frequency = 1;
		have_result = 1;
	}
	if (have_result == 0)
	{
		printf ("No duplicates.");
	}
	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