백준 15748번 Rest Stops

문제

Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For their purposes (and yours), the mountain can be represented as a long straight trail of length L
 meters (1≤L≤106). Farmer John will hike the trail at a constant travel rate of  rF seconds per meter (1≤rF≤106). Since he is working on his stamina, he will not take any rest stops along the way.

Bessie, however, is allowed to take rest stops, where she might find some tasty grass. Of course, she cannot stop just anywhere! There are N rest stops along the trail (1≤N≤105); the i-th stop is xi meters from the start of the trail (0<xi<L) and has a tastiness value ci
 (1≤ci≤106). If Bessie rests at stop i for t seconds, she receives ci⋅t tastiness units.

When not at a rest stop, Bessie will be hiking at a fixed travel rate of rB seconds per meter (1≤rB≤106). Since Bessie is young and fit, rB is strictly less than rF.

Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!

Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.

문제풀이

사용한 알고리즘 : priority_queue

(0) 생각

 Bessie 속력 : 1 meter / R_b sec , John 속력 : 1 meter / R_f sec 입니다.
 예를 들어 3 meter 이동하면, 3*(R_f - R_b) 초 만큼 Bessie가 빨리 도착합니다.

(1) 코드 8~15

 pair< rest stop 위치 , tastiness > 를 priority_queue로 저장할 것입니다.
 약간 그리디 같은데, 가치가 큰 곳을 우선적으로 정렬 할 것입니다.
 가치가 큰 곳부터 쉬는게 무조건 이득이니까요...

(2) 코드 27~37

 현재 위치를 0으로 놓고 탐색을 시작합니다.
 pq에 저장된 쉬는 곳을 순서대로 탐색 하면서, 쉴 수 있다면, 쉬면서 얻게 되는 tastiness를
구하고자 하는 답에 더합니다.