6612 - 개미의 이동

step 1

개미의 위치에만 집중을 해봅시다. 개미가 서로 통과한다고 가정할 때의 위치와 개미가 충돌할 때의 위치가 동일합니다. 즉, 어떤 개미인지는 모르지만 언제 어느 방향으로 개미가 떨어질지는 구할 수 있습니다.

step 2

개미들의 순서에 집중해 봅시다. 왼쪽 개미부터 1, 2, ..., N으로 번호를 매겨봅시다. 개미끼리 서로 뛰어넘지 못하므로 제일 먼저 왼쪽으로 떨어지는 개미는 1번 개미, 다음으로 떨어지는 개미는 2번 개미,... 이런 식으로 떨어집니다. 오른쪽도 마찬가지로 제일 먼저 떨어지는 개미는 N번 개미, 다음은 N-1번 개미,... 이런 식입니다.

언제 어느 방향으로 떨어지는지 알고 있으므로 그때 떨어지는 개미가 어떤 개미인지도 알 수 있습니다. 그럼 이게 모든 개미 변형 문제를 해결할 수 있습니다.(solved.ac에 개미를 검색하면 문제가 많이 나옵니다.)

소스

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
struct data {
	int x;
	char c;
	inline bool operator<(const data& temp)const {
		return x < temp.x;
	}
}b[200000],bb[200000];
int main() {
	int n,i,m;
	while (scanf("%d %d", &n, &m)!=EOF) {
		for (i = 1; i <= m; i++) {
			scanf("%d %c", &b[i].x, &b[i].c);
			if (b[i].c == 'L') { bb[i].x = b[i].x; bb[i].c = 'L'; }
			else { bb[i].x = n - b[i].x; bb[i].c = 'R'; }
		}
		sort(bb + 1, bb + m + 1);
		sort(b + 1, b + m + 1);
		int s = 1, e = m;
		for (i = 1; i <= m; i++) {
			if (i == m - 1 && bb[i].x == bb[i + 1].x) {
				printf("The last ant will fall down in %d seconds - started at %d and %d.\n", bb[i].x, b[s].x, b[e].x);
				break;
			}
			else if (i == m) {
				printf("The last ant will fall down in %d seconds - started at %d.\n", bb[i].x, b[s].x);
				break;
			}
			if (bb[i].c == 'L') s++; else e--;
		}
	}
	return 0;
}