8091 : Petrol

풀이

KOI 주유소 문제에 자동차 연로탱크의 capacity가 추가된 버전(?)

(사실 주유소 문제가 기억 안 나서 맞는지는 모름) 암튼 비슷하다.

시작점에서 끝점까지의 거리가 100만밖에 되지 않는다는 사실!

아하! 그렇다면 시작점으로부터의 거리를 인덱스로 삼는 배열을 하나 만들 수 있겠군!

오, 그럼 자동차를 한 칸씩 움직이면서

연료 탱크 최대값과 가능한 범위 내의 최소 기름값을 잘 관리하면 풀 수 있겠군!!

음… 근데 문제 분류를 어떻게 해야할지 모르겠군

코드

#include <cstdio>
#include <queue>
using namespace std;

int p, n, res, dst, c[1000002];
struct abc {
    int idx, cst;
    bool operator <(abc a)const { return cst>a.cst; }
};
priority_queue<abc> pq;

int main() {
    scanf("%d %d", &p, &n);
    for (int i = 1, x, d; i <= n; i++) {
        scanf("%d %d", &x, &d);
        c[dst] = x; dst += d;
    }
    for (int i = 0; i < dst; i++) {
        if (c[i]) pq.push({ i,c[i] });
        while (!pq.empty() && pq.top().idx <= i-p) pq.pop();
        res += pq.top().cst;
    }
    printf("%d\n", res);
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-27 15:23

Read more posts by this author