Tìm số cuối cùng sau trò chơi loại bỏ min/max bằng C++

Mô tả bài toán

Mảng A n số. Amal và Bimal luân phiên loại bỏ một số. Amal muốn số cuối nhỏ nhất, Bimal muốn lớn nhất. Amal đi trước. Tìm số còn lại.

Ví dụ

A=[2,1,3] → Amal bỏ 3, Bimal bỏ 1 → còn 2.

Thuật toán

Sắp xếp A. Với n phần tử, sau n-1 lượt loại bỏ (Amal loại lớn, Bimal loại nhỏ), số còn lại là phần tử giữa (median). Chỉ số (n-1)/2 (0-based).

Code C++

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

int solve(vector A) {
    sort(A.begin(), A.end());
    return A[(A.size()-1)/2];
}

int main() {
    vector A = {2,1,3};
    cout << solve(A) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {2,1,3}

Output: 2