[BOJ] 2136 - 개미

[백준] 2136 - 개미

기본적인 아이디어는 떨어지는 개미와 같다. 다만 중간에 떨어지는 개미들의 경우에 대해서는 생각하지 않아도 되므로, 가장 마지막에 떨어지는 개미의 시간과 유형만 안다면 바로 답을 구할 수 있다.

소스코드

#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;

vector<PII> ant;

int main(void) {
	int n, b, last_time = 0, type, cnt_l = 0, cnt_r = 0;
	scanf("%d %d", &n, &b);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		if (x > 0) {
			if (last_time < b - x) {
				last_time = b - x;
				type = 1;
			}
			cnt_r++;
			ant.push_back({ x, i });
		}
		else {
			if (last_time < -x) {
				last_time = -x;
				type = -1;
			}
			cnt_l++;
			ant.push_back({ -x, i });
		}
	}
	sort(ant.begin(), ant.end());
	if (type == 1) {
		printf("%d %d\n", ant[n - cnt_r].second, last_time);
	}
	else {
		printf("%d %d\n", ant[cnt_l - 1].second, last_time);
	}
	return 0;
}