MATCHORDER - 출전 순서 정하기 (그리디)

https://algospot.com/judge/problem/read/MATCHORDER

쉬운 문제지만 정당성 증명하는 부분을 유념하기 위한 기록

https://suuntree.tistory.com/103 정당성증명

 

<문제설명>

상대팀의 출전순서가 주어진다. 선수의 능력은 rating 점수로 표현된다. 

우리팀 선수들을 적절히 잘 배치해서 최대승수를 구해라

상대선수 rating <= 우리선수 rating이면 이김

 

 

<풀이>

탐욕적 선택 속성이 성립 ~ '우리 선수 중 opponent[i] 이상의 최소 rating을 가진 선수(u)가 출전하는 것이 최적이다.' 조건 성립

 

opponent[i]에 대항해

2) rating[v]<rating[u]일 때, v가 출전하는 것이 포함된 최적해가 존재한다 가정

 v는 반드시 진다. u는 이기고 있을 수도, 지고 있을 수도 있다.

u와 v의 포지션을 바꾸면

 u는 반드시 이긴다. u가 이기는 상황이었다면 v는 이길수도, 질수도있다. u가 지는 상황이었으면 v는 반드시 진다.

 

 

 승수를 따져봤을 때 u와 v를 바꾸는 것의 승수가 더 높거나 같다. 따라서 u가 포함된 최적해가 존재한다.

 

2) rating[u]<rating[v]일 때, v가 출전하는 것이 포함된 최적해가 존재한다 가정

v는 반드시 이긴다. u는 이기고 있을 수도, 지고있을 수도 있다.

u와 v의 포지션을 바꾸면 ~~~그냥 사진 보자

 

승수를 따져봤을 때 u와 v를 바꾸는 것의 승수가 더 높거나 같다. 따라서 u가 포함된 최적해가 존재한다.

 

1),2) 에 의해 u가 포함된 최적해가 항상 존재한다 따라서 탐욕적 선택 속성이 성립한다.

 

 

 

<코드>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAX = 1e2 + 2;

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		int n, ru[MAX]; multiset<int> ko; cin >> n;
		for (int i = 0; i < n; i++) cin >> ru[i];
		for (int i = 0, u; i < n; i++) {
			cin >> u;
			ko.insert(u);
		}

		int ans = 0;
		for (int i = 0; i < n; i++) {
			int t = ru[i];
			auto it = ko.lower_bound(t);
			if (it != ko.end()) {
				ans++;
				ko.erase(it);
			}
		}
		cout << ans << '\n';

	}
}

 

<생각>

구현은 그냥 multiset에 lowerbound써서 하면된다. 정당성 증명 부분을 눈여겨 보자