h082: 2. 贏家預測

2022.12.11 AM 09:30 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=h082
出題者 : 2022年1月APCS
標籤 : 模擬、陣列
難易度 : 2

解題想法 : 
根據題目定義進行實作即可，但須注意以下幾點 :
1. 兩兩配對時可能會有落單，需要另外判斷。
2. 由於題目會更改S[]和T[]的值，因此必須像題目敘述那樣複製給a,b,c,d再做計算。
3. 若以C/C++實作，記得開long long，Python除法記得用//。
4. 記得計算每個玩家的失敗次數，若大於等於m則不需進入下一輪。

實作上可以真的開一個winner[]，一個loser[]，存放贏家和輸家，最後再合併成為新的idx[]，但要注意winner[]和loser[]清空&合併的時機。

//C language

#include<stdio.h>
int main(){
    int n,m;
    int S[1005], T[1005], idx[1005], times[1005]={0};
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&S[i]);
    for(int i=0;i<n;i++) scanf("%d",&T[i]);
    for(int i=0;i<n;i++) scanf("%d",&idx[i]);
    int idx_size=n;
    while(idx_size > 1){
        int winner[505], loser[505];
        int winner_size=0, loser_size=0;
        for(int i=0;i<idx_size;i+=2){
            int player1, player2;
            if(i == idx_size - 1){
                winner[winner_size++] = idx[i];
                break;
            }
            else{
                player1 = idx[i] - 1;
                player2 = idx[i+1] - 1;
            }
            long long a=S[player1], b=T[player1],
                      c=S[player2], d=T[player2];
            if(a*b >= c*d){
                winner[winner_size++] = player1+1;
                S[player1] = a+(c*d)/(2*b);
                T[player1] = b+(c*d)/(2*a);
                if(++times[player2] < m){
                    loser[loser_size++] = player2+1;
                }
                S[player2] = c+(c/2);
                T[player2] = d+(d/2);
            }
            else{
                winner[winner_size++] = player2+1;
                S[player2] = c+(a*b)/(2*d);
                T[player2] = d+(a*b)/(2*c);
                if(++times[player1] < m){
                    loser[loser_size++] = player1+1;
                }
                S[player1] = a+(a/2);
                T[player1] = b+(b/2);
            }
        }
        idx_size=0;
        for(int i=0;i<winner_size;i++){
            idx[idx_size++] = winner[i];
        }
        for(int i=0;i<loser_size;i++){
            idx[idx_size++] = loser[i];
        }
    }
    printf("%d\n",idx[0]);
    return 0;
}

//C++ language

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m,x;
    cin>>n>>m;
    vector<int>S(n+1,-1),T(n+1,-1),idx,times(n+1,0);
    for(int i=1;i<=n;i++) cin>>S[i];
    for(int i=1;i<=n;i++) cin>>T[i];
    for(int i=0;i<n;i++) cin>>x, idx.push_back(x);
    while(idx.size()>1){
        vector<int>winner,loser;
        for(int i=0;i<(int)idx.size();i+=2){
            int player1,player2;
            if(i+1 == idx.size()){
                winner.push_back(idx[i]);
                continue;
            }
            else{
                player1=idx[i];
                player2=idx[i+1];
            }
            long long a=S[player1], b=T[player1];
            long long c=S[player2], d=T[player2];
            if(a*b >= c*d){
                winner.push_back(player1);
                S[player1] = a + (c*d)/(2*b);
                T[player1] = b + (c*d)/(2*a);
                times[player2]++;
                if(times[player2]<m)
                    loser.push_back(player2);
                S[player2] = c + (c/2);
                T[player2] = d + (d/2);
            }
            else{
                winner.push_back(player2);
                S[player2] = c + (a*b)/(2*d);
                T[player2] = d + (a*b)/(2*c);
                times[player1]++; 
                if(times[player1]<m)
                    loser.push_back(player1);
                S[player1] = a + (a/2);
                T[player1] = b + (b/2);
            }
        }
        idx.clear();
        for(int i:winner) idx.push_back(i);
        for(int i:loser)  idx.push_back(i);
    }
    cout<<idx[0]<<"\n";
    return 0;
}

## Python language

n,m=map(int,input().split())
S=[-1]+[int(x) for x in input().split()]
T=[-1]+[int(x) for x in input().split()]
idx=[int(x) for x in input().split()]
times=[0]*(n+1)
while len(idx)>1:
    winner=[]
    loser=[]
    for i in range(0,len(idx),2):
        try:
            player1,player2=idx[i],idx[i+1]
        except IndexError:
            winner.append(idx[i])
            break
        a,b,c,d=S[player1],T[player1],S[player2],T[player2]
        if a*b>=c*d:
            winner.append(player1)
            S[player1] = a + (c*d)//(2*b)
            T[player1] = b + (c*d)//(2*a)
            times[player2]+=1 
            if times[player2]<m:
                loser.append(player2)
            S[player2] = c + (c//2)
            T[player2] = d + (d//2)
        else:
            winner.append(player2)
            S[player2] = c + (a*b)//(2*d)
            T[player2] = d + (a*b)//(2*c)
            times[player1]+=1 
            if times[player1]<m:
                loser.append(player1)
            S[player1] = a + (a//2)
            T[player1] = b + (b//2)
    idx=winner+loser
print(idx[0])

相關文章

分享此文：