16193 차이를 최대로 2

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

16193번: 차이를 최대로 2

 

정말 간만에 푸는 덱 문제이다. 그리디가 쉬운건 쉬운데, 어려운건 정말 어려운 알고리즘이라고 느낀다.

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    deque<int> arr,ans;
    for(int i=0;i<n;i++){
        int a; cin>>a;
        arr.push_back(a);
    }
    sort(arr.begin(),arr.end());
    ans.push_back(arr.back());
    arr.pop_back();
    while(arr.size()){
        int LL = abs(ans.front()-arr.front());
        int LR = abs(ans.front()-arr.back());
        int RL = abs(ans.back()-arr.front());
        int RR = abs(ans.back()-arr.back());
        int mx = max({LL,LR,RR,RL});
        if(mx==LL){
            ans.push_front(arr.front());
            arr.pop_front();
        } else if(mx==LR){
            ans.push_front(arr.back());
            arr.pop_back();
        } else if(mx==RL){
            ans.push_back(arr.front());
            arr.pop_front();
        } else if(mx==RR){
            ans.push_back(arr.back());
            arr.pop_back();
        }
    }
    long long sum=0;
    for(int i=0;i<n-1;i++) sum+=abs(ans[i]-ans[i+1]);
    cout<<sum;
    return 0;
}