水题你要信了

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

某发最近又认识了很多妹（han）子，可是妹（han）子一多不免有时会忘记那么一两个，为了记得他们的名字，发哥设计了一个记录器。对于每个他刚认识的妹（han）子，他都把妹子的名字放进记录器里，如果记录器已经有这个妹子的名字，则在这个妹子的名字后面加上一个数字（数字从1开始），输出妹子的名字加上数字。若记录器没有这个妹子的记录，则输出OH GOD。

Input:

(EOF)输入一个数字n表示发哥认识的妹子（1<=N<=10^5）,接下来n行每行一个字符串，字符串不超过100个小写字母。

Output:

如描述。

Sample Input:

6firstfirstsecondsecondthirdfirst

Sample Output:

OH GODfirst1OH GODsecond1OH GODfirst2 解题思路：map容器过，并且要用c语言的输入输出，不然老是超时=_=||。map查找时间为O(logn)，总的时间复杂度是O(nlogn)。同样的题目（这题的字符串长度比原来扩大了1倍）链接： AC代码：（225ms）

1 #include
      
        2 using namespace std; 3 int main(){ 4     int t;string str;str.resize(101);//预先分配空间101 5     while(~scanf("%d",&t)){ 6         getchar();map
       
         mp; 7         while(t--){ 8             scanf("%s",&str[0]);//string类用scanf读取 9             if(mp.find(str)==mp.end()){printf("OH GOD\n");mp[str]++;}10             else printf("%s%d\n",str.c_str(),mp[str]++);//string类用c语言格式输出11         }12     }13     return 0;14 }