【Uva 解題筆記】12015 - Google is Feeling Lucky

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3166

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=a130

PDF Source：https://onlinejudge.org/external/120/12015.pdf

題目翻譯：

Google 是最著名的網際網路搜尋引擎之一，它提供和開發了許多網路服務和產品。在其搜尋引擎網站上，有一個有趣的按鈕「好手氣」吸引了我們的目光。這個功能讓使用者可以跳過搜尋結果頁面，直接進入首選頁面。這太省事了，節省了大量時間。

問題是，當使用者輸入一些關鍵字並按下「好手氣」按鈕時，會出現哪個網頁呢？Google 做了很多工作，並提出了優秀的方法來處理這個問題。在這個簡化的問題中，讓我們只考慮 Google 為每個網頁分配一個整數值的相關性。最相關的頁面將被選中。如果有平局，所有具有最高相關性的頁面都可能被選中。

你的任務很簡單，給定 10 個網頁及其相關性。只需挑出所有可能在「好手氣」時提供給使用者的候選網頁。

Input

輸入包含多組測資。測資的數量 T 在輸入檔案的第一行。

對於每組測資，有 10 行，描述網頁和相關性。每一行包含一個不含任何空白字元的字串，表示這個網頁的 URL，以及一個整數 $V_i$ 表示這個網頁的相關性。URL 的長度介於 1 到 100（包含）之間。$(1 ≤ V_i ≤ 100)$

Output

對於每組測資，輸出數行，這些行是可能被選中的網頁的 URL。URL 的順序與輸入相同。請查看範例輸出以獲得更多輸出格式的資訊。

Sample Input

2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
acm.university.edu.cn 9
acm.university.edu.cn 10

Sample Output

Case #1:
www.alibaba.com
www.bad.com
acm.university.edu.cn
Case #2:
www.alibaba.com

精選單字：

relevance (n.) 相關性、實用性、意義
tie 在這裡指的是平分、相等的意思

解題思路：

使用 vector <pair<string, int>> url(10); 容器。

然後使用 max_element() 方法：

1
2
3

int maxNum = max_element(url.begin(), url.end(), [](const pair<string, int>& a, const pair<string, int>& b){
            return a.second < b.second;
        }) -> second;

這邊不要使用 auto，用 pair<string, int>，因為 Uva 是 C++ 11，lambda 還沒有支援 auto。

最後透過 range-based for loop 逐個比較是否與 maxNum 相等，然後產生輸出。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    for (int t = 1; t <= n; ++t){
        vector <pair <string, int>> url(10);
        for (int i = 0; i < 10; ++i){
            string line;
            int num = 0;
            cin >> line >> num;
            url[i].first = line, url[i].second = num;
        }
        int maxNum = max_element(url.begin(), url.end(), [](const pair<string, int>& a, const pair<string, int>& b){
            return a.second < b.second;
        }) -> second;
        cout << "Case #" << t << ":\n";
        for (const auto i : url){
            if (i.second == maxNum){
                cout << i.first << "\n";
            }
        }
    }
    return 0;
}