2013 TCO Round 1B Easy(250) - kusano

まさにこんな感じ。ソートして知識がある人と無い人を組み合わせていったらテストケースは通った。普段の250よりは簡単なはずなので、これでダメなら難しすぎるなと、証明はできないけどサブミットしたら、正解だった。

例えば4人の場合、A1<A2<A3<A4<とすると、A1+A3<min(A1+A4,A2+A3)かつA2+A4>max(A1+A4,A2+A3)が成り立つから……という感じで証明できるのだろうか？

#include <vector>
#include <algorithm>
using namespace std;

class EllysPairs{public:
int getDifference( vector <int> knowledge )
{
    int n = (int)knowledge.size();
    sort( knowledge.begin(), knowledge.end() );
    int mn = 99999999;
    int mx = 0;
    for ( int i=0; i<n/2; i++ )
    {
        mn = min( mn, knowledge[i]+knowledge[n-i-1] );
        mx = max( mx, knowledge[i]+knowledge[n-i-1] );
    }
    return mx - mn;
}};