🔗 UVA-12015 Google is Feeling Lucky

tags: `模擬(Simulation)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

在Google搜尋引擎網站上，有一個名為 “I’m feeling lucky” 的按鈕，該按鈕會直接跳過搜尋結果頁面，直接進入第一個排名的網頁。在這個簡化的問題中，假設每個網頁都有一個整數值表示的相關性。當使用者按下 “I’m feeling lucky” 按鈕時，會顯示最相關的網頁。如果有多個網頁具有相同的最高相關性，這些網頁都有可能被選中。

你的任務是，給定 $10$ 個網頁及其相關性，找出所有可能被選中的網頁，輸出多行表示可能被選中的網頁URL。URL的順序應該與輸入順序相同。

思路：維護最大值

在讀入時將所有網頁及其相關性值存入陣列 $sites$ 中，同時維護最大的相關性值 $mx$ ，最後重新遍歷一次 $sites$ 陣列，輸出所有相關性值等於最大值的URL 即可，如此可以保證輸出順序與輸入順序相同。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為網頁數量，讀入和輸出各需 $\mathcal{O}(n)$ 的時間。
空間複雜度： $\mathcal{O}(n)$ ，需要一個陣列來存放網頁以及其相關性值。

t = int(input())

for kase in range(1, t+1):
    sites = []
    mx = 0
    for _ in range(10):
        url, v = input().split()
        v = int(v)
        sites.append((url, v))
        mx = max(mx, v)
    print(f"Case #{kase}:")
    for url, v in sites:
        if v == mx:
            print(url)

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, kase=1, v;
    string url;
    cin >> t;
    while (t--) {
        vector<pair<string, int>> sites;
        int mx = 0;
        for (int i = 0; i < N; i++) {
            cin >> url >> v;
            sites.push_back({url, v});
            mx = max(mx, v);
        }
        cout << "Case #" << kase++ << ":" << endl;
        for (auto site : sites) {
            if (site.second == mx) {
                cout << site.first << endl;
            }
        }
    }
    return 0;
}