2317번: 결혼식

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


$O(n)$

뒤 n-k개의 데이터에 대해 가장 큰 키와 작은 키를 각각 h,l이라고 하자.
사자들 사이에 h, l를 끼어 넣고보면 n-k개 중 나머지 사람들은 해에 아무런 변화가 없도록 끼어 넣을 수 있다는 것을 알 수 있다.
h는 사자들의 제일 앞, 뒤, 가장 큰 키와 인접한 위치
l는 사자들의 제일 앞, 뒤, 가장 작은 키와 인접한 위치
가 후보지이며 각 경우중 최솟값을 출력한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, k, a[10000], s, h1, l1, h2, l2;
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        if (i&&i < k) s += abs(a[i] - a[i - 1]);
    }
    h1 = *max_element(a, a + k);
    h2 = *max_element(a + k, a + n);
    l1 = *min_element(a, a + k);
    l2 = *min_element(a + k, a + n);
    printf("%d", s + (h2>h1)*min({ h2 - a[0],h2 - a[k - 1],h2 * 2 - h1 * 2 }) + (l1 > l2)*min({ a[0] - l2,a[k - 1] - l2,l1 * 2 - l2 * 2 }));
    return 0;
}