[BAE/<JOON> 문제풀이] 2836. 수상 택시

https://www.acmicpc.net/problem/2836

2836번: 수상 택시

서론

스위핑 문제

풀이

상차지와 하차지가 오름차순인 사람들은 따로 거리를 계산할 필요가 없다. 어차피 상근이는 0에서 m까지 가야하므로 가는 길에 다 태워줄 수 있다.

 

따로 계산해아하는 애들은 상차지와 하차지가 내림차순인 애들이다. 이런 애들은 태우고 내려주고 다시 현재 지점까지 오는데 (상차지 - 하차지) * 2의 추가 이동거리가 발생한다. 이런 추가 거리들만 따로 계산해서 m에서 빼주면 된다.

 

경로가 겹치는 경우의 중복 계산을 피하기 위해 선긋기 문제에서 사용했던 기법을 똑같이 사용하면 된다.

 

출발지 순으로 오름차순 정렬하고 현재 가장 마지막 지점을 저장해가며 아래 3가지 경우를 고려한다.

1. 저장된 마지막 지점이 현재 선분의 끝 지점보다 큰 경우
   이전 선분과 완전히 겹치므로 2, 3번을 고려하지 않는다.
2. 저장된 마지막 지점이 현재 선분의 시작 지점보다 큰 경우
   이전 선분과 끝부분이 겹치므로 추가 선분의 길이는 ( 현재 선분 마지막 지점 - 저장된 마지막 지점 ) 이다.
3. 저장된 마지막 지점이 현재 선분의 시작 지점보다 작은 경우
   이전 선분과 전혀 겹치지 않으므로 추가 선분의 길이는 ( 현재 선분 마지막 지점 - 현재 선분 시작 지점 ) 이다.

코드

/*
* 정방향 + 역방향 선긋기 문제
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ull = long long;
struct line {
	ull s, e; 
};
bool cmp(line a, line b) {
	return a.s < b.s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
	ull n, m; cin >> n >> m; vector<line> arr; 
	for (int i = 1; i <= n; i++) {
		ull s, e; cin >> s >> e;		
		if (s > e) {
			arr.push_back({ e,s });
		}
	}	
	sort(arr.begin(), arr.end(), cmp); ull prev = arr[0].e; ull sum = arr[0].e - arr[0].s;
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i].e > prev) {
			if (arr[i].s >= prev) {
				sum += arr[i].e - arr[i].s;			
			}
			else {
				sum += arr[i].e - prev;
			}
			prev = arr[i].e;
		}
	}
	cout << m + sum * 2;
	return 0;
}