코드 포스(Code Force) 1075 - B. Taxi drivers and Lyft

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1075/problem/B

  끝 없이 이어지는 좌표 상의 선으로 구성된 도시가 있습니다. 이 중에서 매일 도시 거주자들을 태워주는 M명의 택시 기사가 있습니다. 전체 구성원은 N명입니다. 택시 기사를 포함해 모든 N명의 사람들은 고유한 위치에 거주하고 있습니다.

  어떠한 사람이 택시를 부르면, 모든 택시 기사에게 전화를 하는 것이 아니라 자신과 가장 가까운 택시 기사 한 명만 부르게 됩니다. 만약에 거리가 동일한 택시기사가 여러 명이라면, 좌표 상에서 가장 작은 위치를 가진 택시 기사를 부르게 됩니다.

  어느 날 아침에, 택시 기사들은 하나의 의문이 생겼습니다. "매일 각 택시 기사들은 몇 명에게 전화를 받을까?"입니다. 이에 대한 답을 알려주는 프로그램을 작성하면 됩니다.

  예를 들어 일반 주민이 3명, 택시기사가 3명이라고 해봅시다. 이러면 전체 사람이 6명이므로 각각 위치가 주어지고, 각 위치에 따라서 해당 사람이 택시기사라면 1을, 아니라면 0이도록 입력이 주어지는 것입니다.

  전체 사람들의 위치: 2 3 4 5 6 7

  택시 기사들의 위치: 1 0 1 0 1 0

  이 때 택시 기사 3명은 각각 1명씩 전화를 받게 됩니다. 3번 위치의 사람은 2번 위치의 택시 기사에게, 5번 위치의 사람은 4번 위치의 택시 기사에게, 7번 위치의 사람은 6번 위치의 택시 기사에게 말입니다.

  이 문제는 간단히 크기가 2인 슬라이딩 윈도우를 이용해 풀 수 있습니다. 택시기사를 앞에서부터 두 명씩 묶어서 확인하면 돼요. 모든 사람들에 대해서 한 명씩 확인을 하는 건데요. 왼쪽 기사와 오른쪽 기사 사이에 있는 사람은, 더 가까운 기사에게 전화를 걸도록 처리하면 됩니다. 더 뒤쪽에 있는 택시기사의 위치보다 현재 사람의 위치가 크다면 슬라이딩을 수행하여, 그 이후의 택시기사 2명을 보는 방식을 사용합니다.

※ 입출력 예시 ※

input

Copy

3 1
1 2 3 10
0 0 1 0

output

Copy

3 

input

Copy

3 2
2 3 4 5 6
1 0 0 0 1

output

Copy

2 1 

input

Copy

1 4
2 4 6 10 15
1 1 1 1 0

output

Copy

0 0 0 1 

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <vector>

using namespace std;

vector a;
vector taxi;
vector res;

int main(void) {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n + m; i++) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	for(int i = 0; i < n + m; i++) {
		int x;
		cin >> x;
		if(x == 1) {
			taxi.push_back(a[i]);
			res.push_back(-1); // 택시 기사도 주민으로 보므로 초기에 -1로 설정 
		}
	}
	// 택시 기사가 1명이면, 크기가 2인 윈도우를 만들 수 없어 바로 답 출력 후 종료 
	if(taxi.size() == 1) {
		cout << a.size() - 1;
		return 0;
	}
	int now = 0;
	int start = taxi[now];
	int end = taxi[now + 1];
	for(int i = 0; i < a.size(); i++) {
		while(a[i] > end) {
			// 범위 한 칸 슬라이드 
			now++;
			// 마지막 범위인 경우 
			if(now == taxi.size() - 1) {
				// 남은 주민들을 마지막 택시에게 배정하고 종료 
				res[now] += a.size() - i;
				break;
			}
			start = taxi[now];
			end = taxi[now + 1];
		}
		if(now == taxi.size() - 1) break;
		// 현재 주민이 왼쪽과 가까운지, 오른쪽과 가까운지 판별 
		if(a[i] - start <= end - a[i]) {
			res[now]++;
		}
		else {
			res[now + 1]++;
		}
	}
	for(int i = 0; i < res.size(); i++) {
		cout << res[i] << ' ';
	}
	return 0;
}