d566 - 秒殺率

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 ZeroJudge 上提交紀錄的秒殺率。秒殺率定義為第一次提交就 AC 的使用者數量除以 AC 的使用者數量。輸入包含使用者帳號和解題狀況，需要分析紀錄並計算出秒殺率，以百分比形式輸出。

解題思路

使用一個 map (Hash Table) 來儲存每個使用者的最後一次提交結果。遍歷輸入的解題紀錄，如果使用者尚未在 map 中出現，則檢查其提交結果是否為 AC。如果是 AC，則將 AC 人數加一，並將使用者及其結果存入 map。如果使用者已在 map 中，則檢查其先前結果是否為 AC。如果先前結果不是 AC，則更新 map 中的結果。最後，遍歷 map，計算 AC 人數，並計算秒殺率。

複雜度分析

• 時間複雜度: O(n)，其中 n 是解題紀錄的數量。遍歷輸入資料需要 O(n) 時間，遍歷 map 需要 O(m) 時間，其中 m 是不同使用者的數量。在最壞情況下，m 可能等於 n，但通常 m 會小於 n。因此，整體時間複雜度為 O(n)。
• 空間複雜度: O(m)，其中 m 是不同使用者的數量。map 用於儲存每個使用者的最後一次提交結果，因此空間複雜度取決於不同使用者的數量。

程式碼

#include <iostream>
#include <map>
using namespace std;
int main(){
	int p;
	float ac=0,aac=0;
	cin >> p;
	string n,s,ap[p][2];
	map <string ,string> all;
	for(int i=0;i<p;++i)
		cin >> ap[i][0] >> ap[i][1];
	for(int i=p-1;i>=0;--i){
		n=ap[i][0];
		s=ap[i][1];
		if(all.find(n)==all.end()){
			if(s=="AC"){
				++ac;	
			}
			all[n]=s;
		}
		else{
			if(all[n]!="AC"){
				all[n]=s;
			}
		}
	}
	for(auto i=all.begin();i!=all.end();++i){
		if(i->second=="AC"){
			++aac;
		}
	}
	cout << ac/aac*100 << "%";
}