13303 장애물 경기

알고리즘

1. 장애물을 x 좌표 순으로 정렬. 도착지점의 Y좌표와 걸린 길이(y축 이동만 고려)를 저장하는 set을 선언 후, {startY, 0} 를 추가
2. 장애물을 하나씩 꺼내며, 그 장애물에 걸리는 원소만 set에서 꺼내고 하나씩 위로갔을때 거리와 아래로 갔을때 거리를 계산
    이때, 꺼낸 것이 10개여도 장애물의 위 아래 각각에서 최소거리가 걸리는 것만 set에 다시 저장 -> 즉, 10개 여도 2개만 저장됨.
3. 2에서 검사한 원소는 set에서 제거한다.
4. 모든 장애물을 상대로 하면, 이제 최소거리를 구하고, 그때의 y좌표를 저장하고, 출력하면 됨.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
 
struct Line {
	long long x;
	long long yl;
	long long yh;
 
	bool operator < (Line b) {
		return x == b.x ? yl < b.yl : x < b.x;
	}
};
 
int n, starty, endx;
vector<Line> line;
set<pair<long long, long long>> minY;
 
long long min(long long a, long long b) {
	return a < b ? a : b;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> starty >> endx;
	for (int i = 0; i < n; i++) {
		long long a, b, c;
		cin >> a >> b >> c;
		line.push_back({ a,b,c });
	}
	sort(line.begin(), line.end());
 
	minY.insert({ starty, 0 });
 
	for (int i = 0; i < n; i++) {
		vector<pair<long long, long long>> temp;
		set<pair<long long, long long>>::iterator s = minY.lower_bound({ line[i].yl, -200000000000000 });
		set<pair<long long, long long>>::iterator e = minY.upper_bound({ line[i].yh, 200000000000000 });
		long long up = 20000000000000, down = 200000000000000;
		for (set<pair<long long, long long>>::iterator j = s; j != e; ++j) {
			up = min(up, (line[i].yh - j->first) + j->second);
			down = min(down, (j->first - line[i].yl) + j->second);
		}
		minY.erase(s, e);
		minY.insert({ line[i].yh, up });
		minY.insert({ line[i].yl, down });
	}
 
	long long result = 20000000000000;
	vector<int> resultY;
	for (set<pair<long long, long long>>::iterator s = minY.begin(); s != minY.end(); s++) {
		result = min(result, s->second);
	}
	for (set<pair<long long, long long>>::iterator s = minY.begin(); s != minY.end(); s++) {
		if (result == s->second) {
			resultY.push_back(s->first);
		}
	}
 
	cout << result + endx<< "\n";
	cout << resultY.size() << " ";
	for (int i = 0; i < resultY.size(); i++) {
		cout << resultY[i] << " ";
	}
}