ZeroJudge K399: 取貨

學校最近在調查教職員工團購商品的意願，請有意購買的員工來填寫表單。

因為商品非常熱門，因此學校會依員工填答順序來決定領貨的優先順序。若同一位員工填寫多筆訂單，會以他的最後一筆訂單來排順序。

假設每個員工有一個專屬的代表英文字母 (大小寫有別)。如果表單填答紀錄為「cBBADDDc」，表示員工 c 有兩筆訂單、員工 B 有兩筆訂單、員工 A 有一筆訂單、員工 D 有三筆訂單。以每位員工的最後一次填答紀錄來看，領貨順序為 BADc，即員工 B 的領貨序號為 1 號，員工 A、D 和 c 分別為 2、3 和 4 號。

給定表單填答紀錄，請你的程式輸出每一位員工的領貨序號。

範例測資

範例輸入範例輸出
輸入為一段長度不超過 499 個字元的字串，代表表單填答紀錄，其中只會出現大小寫英文字母。請輸出所有員工的領貨序號，輸出時依員工代號字典序 (A, B, C, …, Z, a, b, …, z)，輸出不需有空白字元。
abcde12345
ABCabc123456
aABbCc235146
aaBdccfee214365
cBBADDDc2134
BcabdeAREGCGEEFT71911121081334256

解題思路

可以先將連續的相同字元排除掉。然後跑 For迴圈，並且宣告一個 Map<char, int>，如果目前字元的 Map 值 != 0，就要使用 for(auto it:MAP)，如果 it.second > Map[目前字元]，代表這個字母的順位應該要 -1。另外，還要宣告一個 count 變數預設為 1。for(auto it:MAP) 結束後，將 Map[目前字元] 設為 count-1，如果是新的字元的話就是 Map[目前字元] = count，然後要 count++。

輸出時也是使用 for(auto it:MAP) 來輸入，因為 Map 會自己排序好，所以會從 A 到 z 輸出，只需要輸出 it.second 即可。

範例程式碼－ZeroJudge K399: 取貨

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin >> str;
    map<char, int>MAP;
    int count = 1;
    for (int i = 0; i<str.length(); i++) {
        if (i != 0 && str[i] == str[i-1]) continue;
        if (MAP[str[i]] != 0) {
            for (auto it:MAP) {
                if (it.second > MAP[str[i]]) MAP[it.first]--;
            }
            MAP[str[i]] = count-1;
        }
        else {
            MAP[str[i]] = count;
            count++;
        }
    }
    for (auto it:MAP) {
        cout << it.second;
    }
    cout << "\n";
}

//ZeroJudge K399
//Dr. SeanXD
標籤

相關文章

發佈留言