B. Honest Coach (Codeforces Round #644 Div. 3)

問題

https://codeforces.com/contest/1360/problem/B

問題概要

整数列が与えられる。これを数列AとBに過不足なく分けたとき、Aの最大値とBの最小値の差の絶対値が最小になるようにしたい。

実現可能な差の絶対値の最小値を答えよ。

考察

例えば数列[4, 1, 9, 14, 6]が与えられたとします。この列をソートします。[1, 4, 6, 9, 14]となります。

ここで隣り合う項の差の絶対値をすべて確認します。[3, 2, 3, 5]です。この列は既にソート済みであるため、隣り合う以外の二項の組み合わせの差が、ここに現れた差の最小値を下回ることはありえません。

ここで、差が最小の2となる部分、4と6の間で区切って二つの列に分けます。[1, 4]と[6, 9, 14]です。

元の列はソート済みなので、前者の最大値は最も右にある4ですし、後者の最小値は最も左にある6です。区切った位置は元の数列の二項で作りうる差の最小値であるため、以上で題意を満たしています。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());
        int ans = 1001001001;
        for (int i = 0; i < n - 1; i++) ans = min(ans, a[i + 1] - a[i]);
        cout << ans << endl;
    }
}