h082 - 2. 贏家預測
題目描述
題目描述了 $n$ 個人進行淘汰賽，每個人有戰力 $S$ 和應變力 $T$。比賽規則根據戰力和應變力的乘積大小決定勝負，勝者戰力和應變力會根據公式更新，敗者戰力和應變力也會更新。比賽持續進行，直到只剩下一個人，且敗者達到 $m$ 次失敗則被淘汰。目標是找出最終的贏家編號。
解題思路
這題的核心是模擬整個淘汰賽過程。由於每次淘汰賽都是兩兩比較，因此可以採用貪心策略，每次找到當前陣列中戰力最強的配對進行比賽。
- 初始化：讀取 $n$ 和 $m$，以及每個人的戰力 $S$、應變力 $T$ 和初始排列順序 $idx$。
- 模擬比賽：
- 迴圈直到只剩下一個人。
- 每次迴圈，將當前陣列中的人兩兩配對。
- 根據公式計算勝負，並更新勝者和敗者的戰力、應變力。
- 將勝者放入勝利組，敗者放入失敗組。
- 如果敗者的失敗次數達到 $m$，則將其淘汰。
- 將勝利組和未被淘汰的失敗組合併，形成下一輪的陣列。
- 輸出：輸出最終剩餘的人的編號。
複雜度分析
- 時間複雜度: O(n^2 * m)。最壞情況下，每一輪比賽都需要 O(n) 的時間來配對和計算勝負，總共有 O(n) 輪，且每次淘汰賽需要檢查失敗次數，因此時間複雜度為 O(n^2 * m)。
- 空間複雜度: O(n)。需要使用三個陣列
a,b,c來儲存參賽者資訊，每個陣列的大小都為 O(n)。
程式碼
#include <iostream>
using namespace std;
struct py{
long long s,t,id,l;
};
long long sa[1005],ta[1005];
py a[1005],b[1005],c[1005];
long long n,m;
int main(){
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> sa[i];
}
for(int i=0;i<n;++i){
cin >> ta[i];
}
for(int i=0;i<n;++i){
cin >> a[i].id;
a[i].s=sa[a[i].id-1];
a[i].t=ta[a[i].id-1];
}
while(n>1){
int i=0,j=0,k=0;
while(i<n-1){
if(a[i].s*a[i].t>=a[i+1].s*a[i+1].t){
b[j]=a[i];
b[j].s=a[i].s+a[i+1].s*a[i+1].t/(a[i].t*2);
b[j].t=a[i].t+a[i+1].s*a[i+1].t/(a[i].s*2);
c[k]=a[i+1];
c[k].s=a[i+1].s+a[i+1].s/2;
c[k].t=a[i+1].t+a[i+1].t/2;
}
else{
b[j]=a[i+1];
b[j].s=a[i+1].s+a[i].s*a[i].t/(a[i+1].t*2);
b[j].t=a[i+1].t+a[i].s*a[i].t/(a[i+1].s*2);
c[k]=a[i];
c[k].s=a[i].s+a[i].s/2;
c[k].t=a[i].t+a[i].t/2;
}
c[k].l++;
i+=2;
++j;
++k;
}
if(n%2){
b[j++]=a[n-1];
}
for(int i=0;i<j;++i){
a[i]=b[i];
}
for(int i=j,ii=0;ii<k;++ii){
if(c[ii].l>=m){
--n;
continue;
}
a[i++]=c[ii];
}
}
cout << a[0].id;
}