UVa11991 - Easy Problem from Rujia Liu?(水題)

題目大意：

Rujia Liu(華人大神出了許多演算法競賽的書，被稱之為聖經) 出了一份題目希望讓大家可以一起來為了演算法競賽而努力，題目內容如下：

給你一組陣列，進行查詢，查詢的模式是在 v 此數字出現第 k 次的位置是在陣列中的哪個 index

題目連結

觀念重點

• 能夠快速把此題寫完
• 清空陣列，讓每筆測資不受干擾

分析：

明顯可以看出此題是水體，鼓勵各位新手來進入這個演算法競賽中(地獄)www，這題主要可以用 vector 去解，可以將 vector 開到題目測試資料極限最大值，再將每個數字的 index 不斷存入屬於那個數字的 vector，如果要查詢的 size 比當前的 vector size 大就表示一定沒辦法查詢，輸出 “0”，不然就輸出 num[v][k-1]，vector 的 index 是從 0 開始。

上面講的是基本作法，但有一個地方需要注意

需要特別注意的是我們的數字最大可以來到 \(10^9\)，因此不可以直接用 vector[(10^9)]，如果使用的話會導致 TLE，需要在一個 unordered_map 來進行 hash，由於數字陣列最大只會來到 \(10^5\)，因此讓先讀到的數字先放入 unordered_map，假如沒有被記錄在 unordered_map 表示這個數字還沒有被 hash，現在給他 hash，之後如果查詢此值就給他 hash 過的數值，以此為標準來找出 num[v][k-1] 的值，注意這裡的 num[v][k-1] 是 num[unordered_map[v]][k-1]

map 在數量大於 300 時，速度會開始變慢，如果已知需要紀錄的數量大於 300 時使用 unordered_map。

心得

原本我一開始這題還想要開一個二維陣列去寫，第一個維度是這個數字(定義 x)，第二個維度是出現地次數(定義為 y)，值為題目陣列的 index，但發現這樣很難寫，而且很麻煩XDD，所以後來就改使用 vector 去寫，非常方便又好用阿XD。

題外話：現在在寫 UVA 時 judge 壞掉了，好難過QQQQ。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
using namespace std;
int n, m, k, v, temp; 
vector<int> num[MAXN]; //我們用來分類的陣列，第一個維度是每一個數字的分類
std::unordered_map<int,int> record; //用來記錄 hash，陣列的 int 值會 hash 變成低於 MAXN 的值，才可以讓 num vector 成功存入

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> m){ //輸入資料
        for(int i = 0; i <= MAXN; i++) num[i].clear();
        //一定要把之前的全部查詢都清除，不然會讓上筆測資跟這次的干擾；
        //一定要是 MAXN，題目的數字是 0 < x < MAX
        cnt = 0; record.clear(); //cnt 是 hash 的值，如果 record 沒有紀錄此數字就讓 cnt 表示這值，
        //進行 hash 後就不會有浪費 num vector 的問題。

        for(int i = 1; i <= n; i++){ //輸入資料
            cin >> temp;
            if(!record.count(temp)) record[temp] = cnt++; //如果 record 沒有 hash 過現在這個數值，現在進行 hash，然後讓 cnt 的值再加一。
            num[record[temp]].push_back(i); //將要查詢的數字先轉成 hash 過的值，在用其 hash 值的 num 找出 index。
            //並且透過第二個維度來表示第幾個出現，一開始第一個出現的會是零
        }
        for(int i = 0; i < m; i++){ //查詢 query
            cin >> k >> v;
            if(num[record[v]].size() < k ) cout << "0\n"; //如果 k 比 num[record[v]](hash 值) size 小，表示查詢不到輸出 0
            else cout << num[record[v]][k-1] << '\n'; //輸出 index
        }
    }
    return 0;
}