ZeroJudge F446: Expert Enough

同題:UVa 1237 – Expert Enough

給你 N 筆資料,每筆告訴你工廠名、出產過車子最低和最高價格

共有 Q 組詢問,每組給你一個整數 P

輸出出產車子價格區間包含 P 的工廠名

如果有多間同時符合或沒有半間符合,輸出「UNDETERMINED」

範例測資

範例輸入範例輸出
第一行有個 T 代表測資數(T <= 10)
每筆測資的第一行有一個正整數 D 代表工廠數 (D < 10000)
接下來 D 行每行分別有工廠名(不含空格)和價格區間 L 和 R (0 < L < R < 1000000)
之後有個正整數 Q 代表詢問數
接下來 Q 行每行有一個正整數 P 代表詢問的車子價錢 (0 < P < 1000000)
如果知道是哪間工廠生產的就輸出該工廠名
否則輸出「UNDETERMINED」
1
4
HONDA 10000 45000
PEUGEOT 12000 44000
BMW 30000 75900
CHEVROLET 7000 37000
4
60000
7500
5000
10000
BMW
CHEVROLET
UNDETERMINED
UNDETERMINED

解題思路

使用 Pair<int, int> 將每個工廠的 L 和 R 存起來,將每一個 Pair 存到一個 陣列/Vector 中。

宣告一個 MapKey 值為剛剛收到的 Pair<int, int>Value 值則是工廠名稱

每收到 P 時,使用 For 迴圈存放 L 和 R 的 陣列/Vector 掃描一遍,如果 P 介於某個 L 與 R 的區間,則先將答案設定為目前的 L 與 R 的工廠名稱 (Map 的 Value 值),並且預設一個整數「Count」 計算有幾家工廠符合的變數將其 +1

如果在 For迴圈 中判斷到目前的 Count 已經大於 1 了,則輸出「UNDETERMINED」然後 Break 迴圈。For迴圈 結束之後如果 Count = 1,那就將剛剛設定的答案做輸出,如果 Count = 0,代表沒有這個價位的工廠,也是輸出「UNDETERMINED」。

範例程式碼-ZeroJudge F446: Expert Enough

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

pair<int, int> rtn(int a, int b)
{
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i<T; i++)
    {
        int N;
        cin >> N;
        map<pair<int, int>, string>MAP;
        vector<pair<int, int>>v;
        for (int j = 0; j<N; j++)
        {
            string name;
            int low, high;
            cin >> name >> low >> high;
            pair<int, int>tmp = rtn(low, high);
            v.push_back(tmp);
            MAP[tmp] = name;
        }
        int Q;
        cin >> Q;
        for (int j = 0; j<Q; j++)
        {
            int money, count = 0;
            cin >> money;
            string ans;
            for (auto it:v)
            {
                if (money >= it.first && money <= it.second)
                {
                    count++;
                    ans = MAP[it];
                }
                if (count > 1)
                {
                    cout << "UNDETERMINED\n";
                    break;
                }
            }
            if (count == 1) cout << ans << "\n";
            else if (count == 0) cout << "UNDETERMINED\n";
        }
    }
}

//ZeroJudge F446
//Dr. SeanXD

發佈留言