10819번: 차이를 최대로

https://www.acmicpc.net/problem/10819


$O(n*n!)$


모든 경우를 조사하여 푼다. next_permutation 함수를 쓰면 쉽게 구현할 수 있다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, a[8], maxi, tot;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    do {
        tot = 0;
        for (int i = 0; i < n - 1; i++) tot += abs(a[i] - a[i + 1]);
        maxi = max(maxi, tot);
    } while (next_permutation(a, a + n));
    printf("%d", maxi);
    return 0;
}

$O(n\lg n)$


이 문제는 완전 검색을 할 필요가 없다. n개의 수열을 오름차순 정렬한 수열이 있다고 하자.

i) n이 짝수
m=n/2
작은 것 m개 a1<a2<...<am
큰 것 b1>b2>...>bm이 있다하자.
a1 b1 a2 b2 ...... am bm 과 같이 배열하면 최대이다.

ii)n이 홀수
m=(n-1)/2
작은 것 m개 a1<a2< ... < am
큰 것 m개 b1>b2> ... > bm
중앙값 c가 있다고 하자.

다음 두 배치 중 최댓값을 출력하면 된다.

am-1 b1 a1 b2 a2 ...... bm-1 am-1 bm c
bm a1 b1 a2 b2 ...... am-1 bm-1 am c

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, a[9];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    if (n % 2) printf("%d", 2 * a[n] - min(3 * a[n / 2] + a[n / 2 + 2], 3 * a[n / 2 + 1] + a[n / 2 - 1]));
    else printf("%d", 2 * a[n] - 2 * a[n / 2] - a[n / 2 + 1] - a[n / 2 - 1]);
    return 0;
}