[Silver V] 팔찌 만들기 - 25707

[문제 위치]

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

[문제 풀이]

이 문제는 그리디(정렬/최솟값·최댓값) 를 통해 해결하는 문제이다.
팔찌의 총 줄 길이는 원형에서 인접한 절댓값 차의 합이고, 값을 오름차순으로 배치하면 연속한 차이들의 합이 망원경처럼 소거되어 최댓값−최솟값이 되고 마지막과 처음의 차도 동일하므로 전체 최솟값은 2×(최댓값−최솟값)임을 이용해서 한 번의 스캔으로 최솟값을 구하게 해결한다
아래는 이를 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO;
    int N;
    if (!(cin >> N)) return 0;

    long long mn = LLONG_MAX, mx = LLONG_MIN;
    for (int i = 0; i < N; ++i) {
        long long x; cin >> x;
        mn = min(mn, x);
        mx = max(mx, x);
    }

    cout << 2LL * (mx - mn) << '\n';
    return 0;
}