Question

北大 ACM 1002题 超时

我打算用2个方法做，第一用二维数组，成功accept了；这个用multimap的，修改，提交了20多次，还是Time Limit Exceeded.把代码放下边，大侠帮忙检查下好吧：
#pragma warning(disable : 4786)

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

// 存放规范化后但未处理“重复性”的字符串
multimap <string, int> myMap;

// 最终字符串
// multimap在插入时就自动排好序了
multimap <string, int> myMap_2;

char info[32];

// 规范化
// 思路为： 1. 先将每一行的输入字符串中的字母，转换为数字，即“1234567”形式；
// 2. 再将步骤1中已转换好的格式进行格式的规范，即“123-4567”形式。
string myFormat(string s){

// 将字符串参数转换为对应的字符数组
char inString[32];
s.copy(inString,31,0);
*(inString+31)='\0';

// 声明一个临时存放不含“-”的中间转换数组
char tempS[8];

char mapEle[] = "22233344455566670778889990";
for(int i = 0,j = 0; i < 32;i++){
if(inString[i] == '-')
continue;
if(inString[i] >= 'A' && inString[i] < 'Z')
tempS[j] = mapEle[inString[i] - 'A'];
else
tempS[j] = inString[i];
j++;
}

// 必须令末位字符为'\0'！否则会出现“烫”！
tempS[8] = '\0';
tempS[7] = tempS[6];
tempS[6] = tempS[5];
tempS[5] = tempS[4];
tempS[4] = tempS[3];
tempS[3] = '-';

// 转换为字符串输出
string ss;
ss.assign(tempS);

return ss;
}

int main(void){

// 读内容
int nCases, k;
scanf("%d", &nCases);
for(k = 0; k < nCases; k++){
scanf("%s", info);
// 将已经规范化的字符串存入新的容器中
myMap.insert(multimap <string, int>::value_type (myFormat(info), 1));
}

// 迭代，处理重复的情况
multimap <string, int>::iterator iBegin = myMap.begin();
for(; iBegin != myMap.end(); iBegin++){
int sum = myMap.count(iBegin->first);
if(sum == 1)
continue;
else if(myMap_2.count(iBegin->first) == 0){
myMap_2.insert(multimap <string, int>::value_type (iBegin->first, sum));
cout << iBegin->first << " " << sum;
cout << endl;
}
}

if(myMap_2.empty())
cout << "No duplicates." << endl;

return 0;
}

=======================
解决问题，补送100分

Answer 1

首先，STL里面的容器本身运行速度就是很慢的，而且multimap的插入是O(log n)的，你大量使用遍历和插入肯定是要超时的

对于这个题，你可以研究下用vector <string>去存放，然后使用unique函数去除重复的

具体可以参考
http://www.diybl.com/course/3_program/c++/cppjs/20090522/167676.html