백준 2461번 - 대표선수 소스코드

www.acmicpc.net/problem/2461

2461번: 대표 선수

 

[ 한국정보올림피아드 2011년 시도본선 중등부 3번 대표선수]

★ 우선순위 큐를 이용해서 풀어야 합니다.

edukoi.tistory.com/68?category=841618

19. c++ stl 우선순위 큐

[ 백준 2461번 대표선수 소스코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> ci;

int main()
{
	int n, m, i, j, a;
	int max = -1, min;
	int ans = 2100000000;
	
	ci k;

	vector <int> v[1001];
	int cnt[1001]= {0,};
	//첫번째 항목으로 오름차순 정렬    
	priority_queue<ci, vector<ci>, greater<ci> > q;  
	
	scanf("%d %d", &n, &m);

	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			scanf("%d", &a);
			v[i].push_back(a);
		}
		sort(v[i].begin(), v[i].end());
	}
	
	for(i=0;i<n;i++)
	{
		cnt[i]=1;
		q.push(make_pair(v[i][0], i));
		if(max<v[i][0])
			max = v[i][0];
	}
	
	
	while(!q.empty())
	{
		k = q.top();
		q.pop();
		min = k.first;

		if(ans > max-min)
			ans = max-min;
		
		if(	cnt[k.second] == m) break;
		
		q.push(make_pair(v[k.second][cnt[k.second]], k.second));
		if(max < v[k.second][cnt[k.second]])
		{
			max = v[k.second][cnt[k.second]];	
		} 
		cnt[k.second]++;		
	};
	
	printf("%d", ans);
}