1002.cpp

北大ACM题库中的部分已AC题目源码（1001

#include<iostream>
#include<cmath>
using namespace std;

//快速排序算法

int Partition(int a[],int p,int r)
{
	int i=p;
	int j=r+1;
	int x=a[p];
	int temp;
	while(1)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j)break;
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}

	a[p]=a[j];
	a[j]=x;
	return j;
}

void QuickSort(int a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}

}



int main()
{
	int i,j,k,N;
	int count,flag;
	int tempvalue;
	int valuebyte;
	int *data;
	char chdata[20];
	char tempch[8];
	//输入数据个数
	cin>>N;	
	data=new int[N];
	for(i=0;i<N;i++)
	{
		cin>>chdata;
		valuebyte=0;
		tempvalue=0;
		//对于每一个数据进行格式转换，都转成int型；
		for(j=0;j<strlen(chdata);j++)
		{
			switch(chdata[j])
			{
			case 'A':
			case 'B':
			case 'C':
				tempch[valuebyte]='2';
				valuebyte++;
				break;
			case 'D':
			case 'E':
			case 'F':
				tempch[valuebyte]='3';
				valuebyte++;
				break;
			case 'G':
			case 'H':
			case 'I':
				tempch[valuebyte]='4';
				valuebyte++;
				break;
			case 'J':
			case 'K':
			case 'L':
				tempch[valuebyte]='5';
				valuebyte++;
				break;
			case 'M':
			case 'N':
			case 'O':
				tempch[valuebyte]='6';
				valuebyte++;
				break;
			case 'P':
			case 'R':
			case 'S':
				tempch[valuebyte]='7';
				valuebyte++;
				break;
			case 'T':
			case 'U':
			case 'V':
				tempch[valuebyte]='8';
				valuebyte++;
				break;
			case 'W':
			case 'X':
			case 'Y':
				tempch[valuebyte]='9';
				valuebyte++;
				break;
			case '-':
				break;
			default:
				tempch[valuebyte]=chdata[j];
				valuebyte++;
			}
		}
		tempch[valuebyte]='\0';
	
		data[i]=atoi(tempch);
	}
	//排序
	QuickSort(data,0,N-1);
	count=1;
	flag=0;
	tempvalue=data[0];
	for(i=1;i<N;i++)
	{
		if(data[i]==tempvalue)
			count++;
		else
		{
			if(count==1)
				tempvalue=data[i];
			else
			{
				tempvalue=tempvalue+10000000;
				memset(chdata,'\0',sizeof(chdata));
				sprintf(chdata,"%d",tempvalue);
				chdata[8]='\0';
				for(j=0;j<3;j++)
				{
					chdata[j]=chdata[j+1];
				}
				chdata[j]='-';
				cout<<chdata<<" "<<count<<endl;
				count=1;
				tempvalue=data[i];
				flag=1;
			}
		}		
	}
	if(count!=1)
	{
		tempvalue=tempvalue+10000000;
		memset(chdata,'\0',sizeof(chdata));
		sprintf(chdata,"%d",tempvalue);
		for(j=0;j<3;j++)
		{
			chdata[j]=chdata[j+1];
		}
		chdata[j]='-';
		cout<<chdata<<" "<<count<<endl;
		flag=1;
	}
	if(flag==0)
	{
		cout<<"No duplicates."<<endl;
	}
	return 0;
}