Codeforces Round #445 B. Vlad and Cafes

题目描述

Vlad likes to eat in cafes very much. During his life, he has visited cafes n times. Unfortunately, Vlad started to feel that his last visits are not any different from each other. To fix that Vlad had a small research.

First of all, Vlad assigned individual indices to all cafes. Then, he wrote down indices of cafes he visited in a row, in order of visiting them. Now, Vlad wants to find such a cafe that his last visit to that cafe was before his last visits to every other cafe. In other words, he wants to find such a cafe that he hasn't been there for as long as possible. Help Vlad to find that cafe.

输入

In first line there is one integer n (1 ≤ n ≤ 2·105) — number of cafes indices written by Vlad.

In second line, n numbers a1, a2, ..., a**n (0 ≤ a**i ≤ 2·105) are written — indices of cafes in order of being visited by Vlad. Vlad could visit some cafes more than once. Note that in numeration, some indices could be omitted.

输出

Print one integer — index of the cafe that Vlad hasn't visited for as long as possible.

样例

input

5
1 3 2 1 2

output

input

6
2 1 2 2 4 1

output

提示

Note

In first test, there are three cafes, and the last visits to cafes with indices 1 and 2 were after the last visit to cafe with index 3; so this cafe is the answer.

In second test case, there are also three cafes, but with indices 1, 2 and 4. Cafes with indices 1 and 4 were visited after the last visit of cafe with index 2, so the answer is 2. Note that Vlad could omit some numbers while numerating the cafes.

题目分析

题意：给出一个人n次去过的咖啡厅的号码，求出最长时间没去的咖啡厅

这道题确实是一道水题，但我之前的写法略显复杂，经过队里的大佬的指点后，又想出了一个新写法。

输入的咖啡馆的编号的同时，记录这个咖啡馆访问过的次数。输入完之后，“先进先出”，按照访问的顺序减少对应咖啡馆的访问次数，如果咖啡馆的访问次数减少到0，那么那个咖啡馆的编号就是答案了。

举个例子

咱们来看一下样例1，其中，样例1的访问次序为1 3 2 1 2，完成输入后，可以得到：

咖啡馆编号	1	2	3
访问次数	2	2	1

然后按照访问顺序依次减少访问次数，第一次访问的是1，那么咖啡馆1的访问次数减少到了1，第二次访问的3，那么咖啡馆3的访问次数减少到了0，则3就是答案了。

AC代码

#include<iostream>
using namespace std;
const int N = 1e6 + 1000;
int q[N], s[N];//q用于记录咖啡馆的访问顺序，s记录每个咖啡馆的访问次数
int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> q[i];//记录咖啡馆的访问顺序
        s[q[i]]++;//记录每个咖啡馆的访问次数
    }
    for(int i = 0; i < n; i++){
        s[q[i]]--;//访问次数减少，如果访问次数先减少到0，那么这个
        if(s[q[i]] == 0){//咖啡馆的编号就是答案了
            cout << q[i] << endl;
            return 0;
        }
    }
    return 0;
}

由于本人目前在网上还没看到过类似的做法，所以想放出来分享一下。虽然是一道水题，但是用不同的思路做出来感觉还是蛮有趣的