---
# System prepended metadata

title: 【Uva 解題筆記】12015 - Google is Feeling Lucky
tags: [程式設計, C++, Uva, 競程, CPE, CP]

---

# 【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()` 方法：

```cpp=
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` 相等，然後產生輸出。

範例程式碼：

```cpp=
#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;
}
```

