贏家預測

題目說明

這是一題類似模擬的題目，需要用大量的陣列去做運算。每次模擬的競賽都會有四個數值，分別是雙方的戰力和應變力。當選手輸了一定的次數後就會被淘汰，最後剩下的那位選手獲得勝利。

解題過程

好的，讓我們正式進入解題過程。首先我們要先定義一些巨集，來避免後續撰寫程式時程式碼太長不好閱讀。這段程式碼主要的功能是將前面的縮寫替換成後面真的程式碼。這邊特別需要注意的是，由於題目數值較大，因此我們需要使用 long long 這個較大的型態來儲存數值。

#define pii pair<int, int> // pair 型態縮寫成 pii
#define F first // pair 第一個資料縮寫成 F
#define S second // pair 第二個資料型態縮寫成 S
#define int long long int // 使用 long long 型態替換 int

接下來來宣告這次題目所需要的主要陣列。由於 vector 提供較多的功能可以使用，因此在實際應用中多半使用 vector 而不是傳統陣列。

vector<pii> v; // 儲存選手資料
vector<int> r; // 儲存每輪選手編號
vector<int> fail; // 紀錄選手失敗次數

接下就依據題意讀取資料與儲存。 ln 和 lm 主要是用來暫存，等待之後將他們拼在一起用 pair 儲存。 resize 函式是 vector 用來重設資料大小的方法，像這題會需要讀取 vector 大小做運算的時候就特別實用。

cin >> n >> m;
int ln[n];
int lm[n];
for(int i = 0; i < n; i++){
    cin >> ln[i];
}
for(int i = 0; i < n; i++){
    cin >> lm[i];
}
v.resize(n);
r.resize(n);
fail.resize(n);
for(int i = 0; i < n; i++) {
    v[i] = {ln[i], lm[i]};
}
for(int i = 0; i < n; i++) {
    cin >> r[i];
    r[i]--; // 選手編號從 1 開始，陣列從零，所以要減 1
}

接著我們需要一個主迴圈，用來不斷執行比賽。結束條件為選手只剩下一個，即 r 選手陣列只剩一個資料。

while (r.size() != 1) {
  // 內容
}

接著我們需要處理每一場比賽的資料。由於我們要將贏的選手放在 r 陣列的前面，輸的放後面，所以為了方便起見我們而外撰寫兩個暫存用的陣列 win、lose。

vector<int> win;
vector<int> lose;

接著撰寫迴圈，讓它遍歷每一位選手，並讓他們得以配對。另外透過 / 號我們可以保證當選手數量是奇數時不會執行配對，避免越界存取。

for (int i = 0; i < r.size() / 2; i++) {
  // 每回合中配對的每場比賽
}

接著讀取每場比賽選手的數值。透過 fw 與 bw 來保存前後選手的索引值，方便存取。

int fw = r[i * 2];
int bw = r[i * 2 + 1];
int a = v[fw].F;
int b = v[fw].S;
int c = v[bw].F;
int d = v[bw].S;

接著根據題目敘述，先判斷選手的輸贏後，依照運算規則運算，並將數值存回對應的位置。另外要將輸的選手做紀錄，並且將輸與贏的選手放進暫存的陣列中，用來在下一回戰鬥中調用選手名單。

if(a * b >= c * d) {
  fail[bw]++;
  v[fw].F = a + c * d / (2 * b);
  v[fw].S = b + c * d / (2 * a);
  v[bw].F = c + c / 2;
  v[bw].S = d + d / 2;
  win.push_back(fw);
  if (fail[bw] < m) lose.push_back(bw);
}
else {
  fail[fw]++;
  v[fw].F = a + a / 2;
  v[fw].S = b + b / 2;
  v[bw].F = c + a * b / (2 * d);
  v[bw].S = d + a * b / (2 * c);
  win.push_back(bw);
  if (fail[fw] < m) lose.push_back(fw);
}

在做完所有選手的運算後，我們要檢測是否有選手可以直接晉級。因為題目敘述規定，若有選手數量為奇數，最後一位選手因無法配對可以直接晉級。

if (r.size() % 2 == 1) win.push_back(r[r.size() - 1]);

在完成所有運算後，我們要將一開始宣告的兩個暫存用的陣列重新存到選手名單中。首先先用 resize 將資料大小設為 0 來移除舊資料，再用 insert 插入陣列的資料。

r.resize(0);
r.insert(r.end(), win.begin(), win.end());
r.insert(r.end(), lose.begin(), lose.end());

最後我們要讓程式輸出結果。由於只剩一位選手，因此我們可以保證資料在索引 0 的位置。值得注意的是，由於 r 陣列存的是選手資料在陣列中的索引，而不是選手編號，所以還需要加一來還原回選手編號。

cout << r[0] + 1;

至此你已經學會的整題的邏輯了。這題目沒有太多複雜的演算法，只需要按照題目敘述撰寫即可完成，趕快自己寫來是看看吧！

解題成果

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define F first
#define S second

#define int long long int

int n, m;

vector<pii> v;
vector<int> r;
vector<int> fail;

signed main() {
    cin >> n >> m;
    int ln[n];
    int lm[n];
    for (int i = 0; i < n; i++) {
        cin >> ln[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> lm[i];
    }
    v.resize(n);
    r.resize(n);
    fail.resize(n);
    for (int i = 0; i < n; i++) {
        v[i] = {ln[i], lm[i]};
    }
    for (int i = 0; i < n; i++) {
        cin >> r[i];
        r[i]--;
    }

    while (r.size() != 1) {
        vector<int> win;
        vector<int> lose;
        for (int i = 0; i < r.size() / 2; i++) {
            int fw = r[i * 2];
            int bw = r[i * 2 + 1];
            int a = v[fw].F;
            int b = v[fw].S;
            int c = v[bw].F;
            int d = v[bw].S;

            if(a * b >= c * d) {
                fail[bw]++;
                v[fw].F = a + c * d / (2 * b);
                v[fw].S = b + c * d / (2 * a);
                v[bw].F = c + c / 2;
                v[bw].S = d + d / 2;
                win.push_back(fw);
                if (fail[bw] < m) lose.push_back(bw);
            }
            else {
                fail[fw]++;
                v[fw].F = a + a / 2;
                v[fw].S = b + b / 2;
                v[bw].F = c + a * b / (2 * d);
                v[bw].S = d + a * b / (2 * c);
                win.push_back(bw);
                if (fail[fw] < m) lose.push_back(fw);
            }
        }
        if (r.size() % 2 == 1) win.push_back(r[r.size()-1]);
        r.resize(0);
        r.insert(r.end(), win.begin(), win.end());
        r.insert(r.end(), lose.begin(), lose.end());
    }

    cout << r[0] + 1;
}