[BOJ 2461] 대표 선수(c++)

https://www.acmicpc.net/problem/2461

 

문제 개요

N개의 학급에서 각각 한 명씩 대표 선수를 선발할 때, 선발된 학생들의 능력치 중 최댓값과 최솟값의 차이를 최소화하는 문제입니다.

(1 ≤ N, M ≤ 1,000)

(0 ≤  능력치 ≤ 1,000,000,000)

---

문제 풀이

슬라이딩 윈도우와 우선순위 큐를 활용한 그리디 알고리즘을 통해 문제를 해결하였습니다.

 

• 각 학급의 학생들을 능력치 기준 내림차순으로 정렬
• 초기 상태: 각 학급에서 가장 능력치가 높은 학생 선택
• 현재 선택된 학생들 중 능력치가 가장 높은 학생을 제거하고, 같은 학급의 다음 학생 선택
• 더 이상 선택할 학생이 없을 때까지 반복

---

코드

#include <iostream>
#include <queue>
#include <set>
using namespace std;

int n, m;
priority_queue<int> pq[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x;
			pq[i].push(x);
		}
	}
	set<pair<int, int>> s;
	
	for (int i = 0; i < n; i++) {
		s.insert({ pq[i].top(), i });
		pq[i].pop();
	}
	int res = s.rbegin()->first - s.begin()->first;
	while (true) {
		int idx = s.rbegin()->second;
		s.erase(*s.rbegin());
		if (!pq[idx].empty()) {
			s.insert({ pq[idx].top(), idx });
			pq[idx].pop();
		}
		else {
			break;
		}
		res = min(res, s.rbegin()->first - s.begin()->first);
	}
	cout << res;
	return 0;
}