e592 - 10142 - Australian Voting
題目描述
題目描述了澳大利亞的投票系統，選民需要對候選人進行排名。程式需要模擬這個投票過程，直到有候選人獲得超過 50% 的選票，或者所有候選人並列。
解題思路
程式使用貪心策略模擬投票過程。首先，計算每個候選人獲得的第一順位選票數量。如果某個候選人獲得超過 50% 的選票，則該候選人獲勝。否則，找出獲得選票最少的候選人，並將其淘汰。然後，更新選票，將淘汰候選人之後的候選人順序往前移動。重複此過程，直到有候選人獲勝或所有候選人並列。
複雜度分析
- 時間複雜度: O(n * m * k)，其中 n 是候選人數量，m 是選票數量，k 是每張選票的長度（最多為候選人數量）。
- 空間複雜度: O(n * m)，主要用於儲存選票數據。
程式碼
#include <bits/stdc++.h>
using namespace std;
int t,n,v[1005][25],sz;
string a[25],s;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(cin >> t;t--;){
cin >> n;
int wa[25]={};
getline(cin,s);
for(int i=0;i<n;++i)
getline(cin,a[i]);
memset(v,0,sizeof(v));
for(;getline(cin,s)&&s.size();++sz){
stringstream ss(s);
for (int i=0;i<n;++i)
ss >> v[sz][i];
}
for(int re=n;re>0;){
int fr[25]={},mi=1e9,ma=-1e9,num=0,id,buf[25];
for(int i=0;i<sz;++i)
for(int j=0;j<n;++j)
if(wa[v[i][j]-1]==0){
fr[v[i][j]-1]++;
break;
}
for(int i=0;i<n;++i)
if(wa[i]==0){
mi=min(mi,fr[i]);
if(fr[i]>ma){
id=i;
buf[0]=i;
num=1;
ma=fr[i];
}
else if(fr[i]==ma)
buf[num++]=i;
}
if(num==re||ma*2>sz){
for(int i=0;i<num;++i)
cout << a[buf[i]] << "\n";
break;
}
for(int i=0;i<n;++i)
if(wa[i]==0&&fr[i]==mi)wa[i]=1,--re;
}
if(t)cout << "\n";
}
}