코드 복사/붙여넣기 하는 당신이 아름답습니다.

2786 : 상근이의 레스토랑

풀이

(첫 주문) 가격과 (일반 주문) 가격이 나누어져있다.

일반 가격으로 정렬한 뒤 1~i번째 가격의 합을 구해놓고 생각하자.

그럼 두 가지의 케이스로 나눌 수 있다.

  1. 1~i번째 메뉴들 중 (첫 주문)과 (일반 주문) 가격의 차이가 가장 큰 것을 고르는 경우

  2. 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

wookje.kwon's profile image

wookje.kwon

2017-09-03 00:46

Read more posts by this author