백준] 6160 - Election Time(USACO 2008)

시간 제한 : 1초

메모리 제한 : 128MB

입력

Line 1: Two space-separated integers: N and K

Lines 2..N+1: Line i+1 contains two space-separated integers: A_i and B_i

출력

Line 1: The index of the cow that is expected to win the election.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct cow {
	int first;
	int second;
	int originIdx;
};
bool compare(const struct cow &a, const struct cow &b) {
	return a.first > b.first;
}
int main(void)
{
	int n, k, max, maxIdx;
	cin >> n >> k;
	vector<struct cow> arr(n);
	for (int i = 0, a, b; i < n; i++)
	{
		cin >> a >> b;
		arr[i].first = a;
		arr[i].second = b;
 		arr[i].originIdx = i + 1;
	}
	sort(arr.begin(), arr.end(), compare);
	max = arr[0].second;
	maxIdx = arr[0].originIdx;
	for (int i = 0; i < k; i++)
	{
		if (max < arr[i].second)
			max = arr[i].second, maxIdx = arr[i].originIdx;
	}
	cout << maxIdx;
}

Tip

정렬과 최댓값 구하기 문제로 구조체를 이용한 정렬을 활용하면 빠르게 풀어낼 수 있다.