최소 최대 제거 게임 후 최종 숫자를 찾는 C++ 코드

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. 칠판에 n개의 숫자가 쓰여져 있다. Amaland Bimal은 턴제 게임을 하고 있습니다. 각 차례에 숫자를 선택하고 보드에서 제거합니다. 아말이 먼저 플레이합니다. Amal은 보드에 남겨둘 마지막 숫자를 최소화하기를 원하고 Bimal은 최대화하기를 원합니다. 우리는 칠판에 남을 번호를 찾아야 합니다.

따라서 입력이 A =[2, 1, 3]과 같으면 출력은 2가 됩니다. Amal은 3을 제거하고 Bimal은 1을 제거하므로 최종 숫자는 2가 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of A
sort the array A
return A[floor of ((n - 1)/2)]

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
   int n = A.size();
   sort(A.begin(), A.end());
   return A[(n - 1) / 2];
}
int main(){
   vector<int> A = { 2, 1, 3 };
   cout << solve(A) << endl;
}

입력

{ 2, 1, 3 }