POJ-1002-487-3279-解题报告

很久之前就做过这道题了，只是当时一直TLE。其实当时也能得到正确答案，不过由于用了STL map这些东西，可能效率比较低导致TLE。今天彻底用C做出来了。

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

const int MAX_CASE_SIZE = 100003;
const int MAX_STD_PHONE_SIZE = 10;

char phone[128]; //接收电话电码输入
char stdPhone[MAX_CASE_SIZE][MAX_STD_PHONE_SIZE]; //存储标准电话号码
char map[] = "22233344455566677778889999"; //采用一个数组将号码的字母映射到数字

/*将电话号码转为标准形式，并存储在stdPhone[n]中*/
void changeToStdPhone(int n) {
    //printf("%s/n", phone);
    int stdIndex = 0;

    for(int i = 0; phone[i] != '/0'; i++) {
        if(stdIndex == 3) {
            stdPhone[n][3] = '-';
            stdIndex++;
            i--; //回退
            continue;
        }

        if(phone[i] == '-')
            continue;

        if(phone[i] >= '0' && phone[i] <= '9') {
            stdPhone[n][stdIndex] = phone[i];
            stdIndex++;
        } else {
            stdPhone[n][stdIndex] = map[phone[i] - 'A'];
            stdIndex++;
        }
    }
}

/*qsort使用的比较函数*/
int cmp(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

int main()
{
    int nCase;
    scanf("%d", &nCase);

    for(int i = 0; i < nCase; i++) {
        scanf("%s", phone);
        changeToStdPhone(i);
    }

    /*将标准号码从小到大排序*/
    qsort(stdPhone, nCase, sizeof(char) * MAX_STD_PHONE_SIZE, cmp);

    bool isDup = false;
    int i, j;
    for(i = 0; i < nCase; i = j) {
        j = i + 1;
        for(; strcmp(stdPhone[i], stdPhone[j]) == 0; j++)
            ;

        /*输出重复的电话号码*/
        if(j > i + 1) {
            isDup = true;
            printf("%s %d/n", stdPhone[i], j - i);
        }
    }

    if(!isDup)
        printf("No duplicates.");

    return 0;
}