[algospot] MATCHORDER

문제링크 입니다

[MATCHORDER] 문제 😊😊😊😊😊

전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다.\ 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다.\ 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순서를 알려 주어야 합니다.

결승전 이틀 전, 한국팀의 유감독은 첩보를 통해 상대 러시아팀의 출전 순서를 알아냈습니다. 이 대회에서는 각 선수의 실력을 레이팅(rating)으로 표현합니다.\ 문제를 간단히 하기 위해 1:1 승부에서는 항상 레이팅이 더 높은 선수가 승리하고, 레이팅이 같을 경우 우리 선수가 승리한다고 가정합시다.

표와 같이 출전 순서를 정했다고 하면 한국팀은 2번, 3번, 5번, 6번 경기에서 승리해 전체 네 경기를 이기게 됩니다. 그러나 대신 4번 경기와 1번 경기에 나갈 선수를 바꾸면 1번 경기만을 제외하고 모든 경기에 승리할 수 있지요. 상대방 팀 선수들의 순서를 알고 있을 때, 어느 순서대로 선수들을 내보내야 승수를 최대화할 수 있을까요?

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C≤50)가 주어집니다.\ 각 테스트 케이스의 첫 줄에는 각 팀 선수의 수 N(1≤N≤100)가 주어집니다.\ 그 다음 줄에는 N개의 정수로 러시아팀 각 선수의 레이팅이 출전 순서대로 주어지며, 그 다음 줄에는 N개의 정수로 한국팀 각 선수의 레이팅이 무순으로 주어집니다.\ 모든 레이팅은 1 이상 4000 이하의 정수입니다.

출력

각 테스트 케이스마다 한 줄에 한국팀이 얻을 수 있는 최대 승수를 출력합니다.

입력 예제

3
6
3000 2700 2800 2200 2500 1900
2800 2750 2995 1800 2600 2000
3
1 2 3
3 2 1
4
2 3 4 5
1 2 3 4

출력 예제

5
3
3

전체 코드는 다음과 같습니다.

//
//  MATCHORDER.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/17.
//


#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

ifstream fin("MATCHORDER.txt");
int N; //선수의수
int match(const vector<int>& korea, const vector<int>& russia){
    int count =0;
    multiset<int> ratings(korea.begin(), korea.end());
    for(int rus =0; rus<N; rus++){
        if(*ratings.rbegin() < russia[rus]){
            ratings.erase(ratings.begin());
        }
        else{
            ratings.erase(ratings.lower_bound(russia[rus]));
            count++;
        }
    }
    return count;
}
int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;

    for(int Test = 0; Test < test_case; Test++){
        fin>>N;
        vector<int> korea;
        vector<int> russia;
        for(int i=0; i<N; i++){
            int rus;
            fin >> rus;
            russia.push_back(rus);
        }
        for(int i = 0; i<N; i++){
            int kor;
            fin >> kor;
            korea.push_back(kor);
        }

        cout << match(korea,russia) << endl;
    }
    return 0;
}