ZeroJudge E541: Where is the marble

同題：UVa 10474 – Where is the marble

Raju 和 Meena 喜歡玩大理石 (Marble)。他們有很多上寫有數字的大理石。
剛開始，Raju 會按照書寫在上面的數字以升序依次放置大理石。
然後，Meena 會要求 Raju 找到指定號碼的第一塊大理石。
如果 Raju 成功，Raju 將獲得一分，如果 Raju 失敗，Meena 將獲得一分。
經過多次的詢問，遊戲結束，獲得最高分的玩家獲勝。
今天，你有機會幫助 Raju。但是請不要小看 Meena，她寫了一個程式來追蹤你花多少時間才能給出所有答案。
因此，你也必須寫了一個有效率的程式，來確保勝利。

範例測資

範例輸入範例輸出
EOF 輸入，每組測資開頭有兩個整數 N 和Q。
N 是大理石的數量，Q 是 Meena 的查詢數量。
如果 N = Q = 0 代表輸入結束。
接下來 N 行包含 N 個大理石上寫的數字。這些大理石編號不會以任何特定順序出現。
接下來的 Q 行將進行 Q 次查詢。
所有數字皆 <= 10000，並且不為負數。		對於每組測資，輸出測資編號。
對於每個查詢，如果在位置y上找到第一個編號為 x 的大理石
輸出「x found at y」
如果沒有編號為 x 的大理石
輸出「x not found」
4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0		CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3
ZeroJudge E541 範例測資

解題思路

先將 N 個石頭的編號收到一個陣列中並且排序，再來宣告一個 Map<int, int>，並且跑 For迴圈從 0 跑到 N-1，如果 Map[陣列[i]] 為 0，則 Map[陣列[i]] = i + 1。因為如果有重複出現的數字要取最前面那個所以要先判斷 Map 中是否已經存在某數的位置了。

輸出時判斷要查詢的數字是否存在於 Map 中，如果 Map[數字] == 0 代表沒有這個數字輸出「not found」，否則輸出 Map[數字]。

範例程式碼－ZeroJudge E541: Where is the marble

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, Q, count = 1;
    while (cin >> N >> Q && N != 0 && Q != 0)
    {
        vector<int>num;
        for (int i = 0; i<N; i++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        sort(num.begin(), num.end());
        map<int, int>MAP;
        for (int i = 0; i<N; i++)
        {
            if (MAP[num[i]] == 0) MAP[num[i]] = i+1;
        }
        cout << "CASE# " << count << ":\n";
        for (int i = 0; i<Q; i++)
        {
            int tmp;
            cin >> tmp;
            if (MAP[tmp] == 0) cout << tmp << " not found\n";
            else cout << tmp << " found at " << MAP[tmp] << "\n";
        }
        count++;
    }
}

//ZeroJudge E541
//Dr. SeanXD
標籤

相關文章

發佈留言