10919 - 선물상자

step 1

각 사람들한테 선물을 주었을 때 아만이 왼쪽으로 출발했는지 오른쪽으로 출발했는지 기록해 두었다고 가정합니다.

 

이렇게 했을 때 왼쪽과 오른쪽이 번갈아 가면서 나올 수 있을까요? 그 경우 순서를 바꿔서 더 최적인 상황을 만들 수 있습니다.

 

이것을 반복하다 보면 특정 위치를 기준으로 한쪽은 왼쪽, 다른 쪽은 오른쪽만 있게 됩니다. 이것을 왼쪽 사람과 오른쪽 사람으로 부르겠습니다.

 

그럼 모든 가능한 경계선에 대해 답을 구하면 쉽게 해결할 수 있습니다.

step 2

사람들을 위치 기준으로 정렬합니다. 출발점에서 가장 멀리 떨어진 오른쪽 사람한테 선물을 준다고 생각해 봅시다. 그럼 나머지 선물은 2, 3,..., K번째 오른쪽 사람한테 줘야 합니다.

dp-r[i]: i번째 사람이 가장 먼 오른쪽 사람이고 오른쪽 사람한테만 선물을 나눠준다 했을 때 최소한의 이동 횟수

 

라고 할 때

dp-r[i] = dp-r[i-k] + min({한 바퀴 돌 때의 거리, 갔다가 다시 돌아올 때의 거리})

 

를 만족합니다. 왼쪽 사람도 같은 방식으로 해결할 수 있습니다. 

이 값이 있으면 문제의 답을 구할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
#include<queue>
using namespace std;
long long int bb[20000000],rr[20000000],ll[20000000];
long long int delivery(long long int n, long long int m, long long int l, long long int* b) {
	long long int i,minn=9000000000000000000ll,tar;
	sort(b, b + n);
	for (i = 0;i < n;i++) {
		long long int pr = 0;
		if (i >= m) pr = rr[i - m];
		if (bb[i] <= l / 2) pr += bb[i] * 2; else pr += l;
		rr[i] = pr;
	}
	for (i = n-1;i >= 0;i--) {
		long long int pr = 0;
		if (i <= n - m) pr = ll[i + m];
		if ((l - bb[i]) <= l / 2) pr += (l - bb[i]) * 2; else pr += l;
		ll[i] = pr;
	}
	for (i = 0;i <= n;i++) {
		tar = 0;
		if (i == 0) tar = ll[0];
		else tar = rr[i - 1] + ll[i];
		minn = min(minn, tar);
	}
	return minn;
}
int main() {
	long long int n, m, l,i;
	scanf("%lld%lld%lld", &n, &m, &l);
	for (i = 0;i < n;i++) {
		scanf("%lld", &bb[i]);
	}
	printf("%lld", delivery(n, m, l, bb));
	return 0;
}