a130 - 12015 - Google is Feeling Lucky

🔗 前往 ZeroJudge 原題

題目描述

題目要求模擬 Google 的「好手氣」功能。給定 10 個網頁及其相關度，找出相關度最高的網頁，並輸出所有相關度等於最高相關度的網頁名稱。有多組測試案例。

解題思路

程式碼首先讀取測試案例的數量。對於每個測試案例，程式碼讀取 10 個網頁名稱和相關度，並找出最大的相關度。然後，程式碼遍歷所有網頁，輸出所有相關度等於最大相關度的網頁名稱。此解法使用簡單的迭代和比較來找到最大值並輸出結果。

複雜度分析

• 時間複雜度: O(N)，其中 N 是每個測試案例中網頁的數量 (在本例中為 10)。程式碼需要遍歷所有網頁兩次：一次找到最大相關度，另一次輸出相關度等於最大相關度的網頁。
• 空間複雜度: O(1)。程式碼使用固定大小的陣列 d 來儲存網頁名稱和相關度，陣列大小為 10，因此空間複雜度是常數。

程式碼

#include <iostream>
#include <string>
using namespace std;
struct c{
	string n;
	int v;
}d[10];
int main(){
	int a;
	string b;
	cin >> a;
	for(int c=1;c<=a;c++){
		int max=0;
		for(int i=0;i<10;i++){
			cin >> d[i].n >> d[i].v;
			if(d[i].v>max)
				max=d[i].v;
		}
		cout << "Case #" << c << ":\n"; 
		for(int i=0;i<10;i++){
			if(d[i].v==max){
				cout << d[i].n << "\n";
			}
		}
	}
}