nails.cpp

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

void qsort(int a[100], int l, int r);

int main(){

    int MAX = 10010;

    int ar[100];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> ar[i];

    if (n == 2){
        cout << abs(ar[1] - ar[0]) << endl;
        return 0;
    }

    qsort(ar, 0, n - 1);


    int ans[101], a1, a2;
    ans[0] = ar[1] - ar[0];
    ans[1] = ans[1] + ar[2] - ar[1];

    for (int i = 2; i < n; i++){
        a1 = ans[i - 1] + (ar[i] - ar[i - 1]);
        a2 = ans[i - 2] + (ar[i] - ar[i - 1]);
        if (a1 < a2)
            ans[i] = a1;
        else
            ans[i] = a2;
    }

    cout << ans[n - 1] << endl;

    return 0;
}

void qsort(int a[100], int l, int r){
    int m = a[(l + r) / 2];
    int i = l, j = r;
    do {
        while (a[i] < m)
            i++;
        while (a[j] > m)
            j--;
        if (i <= j){
            if (a[i] > a[j])
                std::swap(a[i], a[j]);
            i++;
            j--;
        }
    } while(i <= j);
    if (i < r)
        qsort(a, i, r);
    if (j > l)
        qsort(a, l, j);
}


//  ---*-*--*------*-*-*
//    0*1*  2*    3*4*5*

//  ---*-*--*--*-*-*
//    0*1* 2* 3*4*5*
//    0*1* 3* 3*4*5*