[백준] 15748번 Rest Stops

15748번: Rest Stops

가치가 가장 큰 stop부터 가야 하므로 가치를 기준으로 내림차순 정렬한다.

 

stop에서 Bessie가 쉴 수 있는 시간은

(John의 1미터 당 걸리는 시간 - Bessie의 1미터 당 걸리는 시간) * (현재 stop - 이전 stop까지 온 거리)

이다.

 

여기서 Bessie가 가질 수 있는 가치는

쉴 수 있는 시간 * 현재 stop에서 얻을 수 있는 가치

이고 이 값을 result에 계속 더해서 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
vector <pair<int, int>> v;
int main() {
	long long L, N, Bessie, John, x, c;
	cin >> L >> N >> John >> Bessie;
	for (int n = 0; n < N; n++) {
		cin >> x >> c;
		v.push_back(make_pair(c, x));
	}
	sort(v.begin(), v.end(), greater<>());
	long long current = 0, res = 0;
	for (int i = 0; i < v.size(); i++) {
		if (current < v[i].second) {
			res += (John - Bessie) * (v[i].second - current) * v[i].first;
			current = v[i].second;
		}
	}
	cout << res;
	return 0;
}