풀이
(첫 주문) 가격과 (일반 주문) 가격이 나누어져있다.
일반 가격으로 정렬한 뒤 1~i번째 가격의 합을 구해놓고 생각하자.
그럼 두 가지의 케이스로 나눌 수 있다.
-
1~i번째 메뉴들 중 (첫 주문)과 (일반 주문) 가격의 차이가 가장 큰 것을 고르는 경우
-
i~n번째 메뉴들 중 (첫 주문)의 가격이 가장 작은 것을 고르는 경우
이제 어찌저찌여차저차 잘 짜면 된다.
코드
#include <stdio.h>
#include <algorithm>
#define fst first
#define snd second
using namespace std;
typedef pair<int, int> pii;
int n, k, mn[500001];
long long sum;
pii p[500001];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d %d", &p[i].fst, &p[i].snd);
sort(p, p + n, [](const pii &i, const pii &j) { return i.snd < j.snd; });
mn[n] = 2e9;
for (int i = n - 1; i >= 0; i--) mn[i] = min(p[i].fst, mn[i + 1]);
for (int i = 0; i < n; i++) {
if (p[k].snd - p[k].fst < p[i].snd - p[i].fst) k = i;
sum += (long long)p[i].snd;
printf("%lld\n", min(sum - p[k].snd + p[k].fst, sum - p[i].snd + mn[i]));
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge