UVa1237 - Expert Enough?(水題)

題目大意：

有一家公司要建立汽車資料庫，會給你很多筆的汽車品牌與他的最低價與最高價，之後在給你一個價格請你幫忙查詢此價格有哪一個汽車品牌落在區間？

如果這個價格有兩個汽車品牌以上的話或都沒有汽車品牌在此價格就輸出 UNDETERMINED，其他都輸出牌子。
題目連結

觀念重點

• 選擇適合的演算法
• 評估程式好寫以及題目最大容許的時間複雜度

分析：

這題其實用程式碼寫可以非常簡單，不然怎麼可以叫水題嘛XD，但這題可以直接用線性查詢的方式查出，由於題目的資料庫資料最大只會來到 10000，且查詢只會有 1000，因此這題的時間複雜度可以到 \(O(10^7)\)，基本上所有的程式題目都會容許此時間複雜度，因此我們就直接用最暴力的方式解即可。

建議 UVA 的題目都已嚴格輸出為導向，我有時候常常會因為這個卡很久QQ。

心得

其實這題我原本是想要用線段樹來解的，但寫到一半發現，要離散化的線段樹我沒有寫過呀QQQ，如果要寫要花很多時間呀，而且中途有遇到很多障礙QQ。

後來在翻網路資料時，意外看到有篇說這題可以暴力輾過，我才想起這題的時間複雜度不高呀，我為甚麼要讓自己走 hard 路線了，應該走 easy 路線呀！

對於每份題目，應該要能夠寫出最符合題目要求且讓自己編寫速度最快的演算法，畢竟比賽分秒必爭，AC 卻不看程式碼的品質。

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 10020
#define LOCAL
using namespace std;
int t, h, m, l, p, d, q; //題目的輸入資訊
struct Com{
    int l, r; //l 最低價格 r 最高價格
    string v; //v 公司名子
};
Com com[MAXN];

string solve(int p){
    string name = ""; //輸出汽車品牌
    for(int i = 0; i < d; i++){ //開始暴力查詢
        if(p >= com[i].l && p <= com[i].r){ //如果在此區間就進入 if
            if(name == "" ) name = com[i].v; //如果還沒有被輸入汽車品牌，那就輸入
            else return "UNDETERMINED";
            //表示前面有被輸入，這個價格有兩個以上的汽車品牌，因此輸入  "UNDETERMINED"
        }
    }
    if(name == "" ) name = "UNDETERMINED"; //沒有品牌，輸輸=入  "UNDETERMINED"
    return name; // 輸出 name
}

int main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> d;
        for(int i = 0; i < d; i++) cin >> com[i].v >> com[i].l >> com[i].r;
        //資料庫輸入
        cin >> q;
        string name;
        for(int i = 0; i < q; i++){ //查詢
            cin >> p;
            name = solve(p);
            cout << name << '\n';
        }
        if (t != 0) cout << '\n';
    }

}