풀이
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이