同題: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 中。
宣告一個 Map ,Key 值為剛剛收到的 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