Registration system / 注册系统

CodeForce Round 4 C

题目连接：CF4C

题目描述

A new e-mail service "Berlandesk" is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that‘s why they ask you to help. You‘re suggested to implement the prototype of site registration system. The system should work on the following principle.

Each time a new user wants to register, he sends to the system a request with his name. If such a name does not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration. If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1, name2, ...), among these numbers the least ii is found so that name ii does not yet exist in the database.

输入格式

The first line contains number nn ( 1<=n<=10^{5}1<=n<=105 ). The following nn lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.

输出格式

Print nn lines, which are system responses to the requests: OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.

题意翻译

题目背景

一个名为"Berlanddesk"的电子邮件系统即将在Berland上线运营。该电子邮件系统的管理员希望整个系统的建设可以尽早完成，因此他们找到了资深程序员您，希望您能够为他们开发一个用户注册系统的原型产品。

该系统的运行遵循以下原则:

新用户注册时，他将向系统发送一则内容为其用户名的请求，如果该用户名尚未存在于系统数据库内，则将该用户名插入数据库，同时用户得到回应信息"OK"表示其已经成功注册。如果用户请求的用户名已经存在于数据库内，那么系统将产生一个新的用户名并将其加入数据库。新用户名由用户请求的用户名与正整数i构成，i为使"用户名i"尚未存在于数据库内的最小的i。

输入格式

第一行一个整数n(1<=n<=10^5)。接下来n行，每行表示用户向系统发出的一则请求。每行内容均非空且均为由至多32个小写拉丁字母组成的字符串。

输出格式

n行，每行表示系统对一则请求做出的回应。如果该用户名尚未存在于系统数据库内，则输出"OK"。如果用户请求的用户名已经被注册，则输出依照规则生成的新用户名。

输入输出样例

输入 #1

4
abacaba
acaba
abacaba
acab

输出 #1

OK
OK
abacaba1
OK

输入 #2

6
first
first
second
second
third
third

输出 #2

OK
first1
OK
second1
OK
third1

思路

题意

整个题目的大概意思就是找重复值，没有重复过就直接输出OK，如果重复就输出原字符串+重复的次数。

类似于在桌面新建文件夹，有重名的就在后面加一个标号。

最开始想到的

读题后，想直接进行模拟。输入用户名然后存入，在从数组中查找，找到一次统计量count就加一次。然而，题目的数据量是\(10^5\),而且是字符串，直接模拟然后查找必然会超时。

简单优化

超时是因为对于每一个新加入的数据，都需要从头查到尾，举一个最极端的例子，假如输入100个字符串，全部都是“Hello”，可以发现，我们循环查找的次数分别是\(1,2,3……100\)。对于这些重复的字符串我们能不能把统计的结果记下来，减少重复搜索呢？显然这是可以的。对于每次加入的重复的字符串，它们的值已经存储了，增加的只是数量，我们可以另开一个数组记录这个数量。

参考代码

//CF4C_Registration system 
#include<bits/stdc++.h>
#define MAXN 100000
using namespace std;
string name[MAXN + 5];//存储用户名,相同用户名只存储一次，重复输入只增加对应的cnt数 
int cnt[MAXN + 5];//存储用户名出现的次数

int main(){
    int n;
    string s;
    int num = 0;//记录输入的 不同的 用户名的数量 
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        bool flag = 0;
        cin >> s;
        for(int j = 0; j < num; j++){
            if(name[j] == s){
                cnt[j]++;//找到相同的，记录+1 
                cout << s << cnt[j] << endl;
                flag = 1;
                break;
            } 
        }
        if(flag == 0){//未找到相同的，添加新记录再输出 
            name[num] = s;
            num++;
            cout << "OK" << endl; 
        }
    } 

    return 0;
}