[1] はじめに

この問題は、高度な知識を全く要求せず、実装もとても軽いですが、最初の着眼点に気付けるかどうかが重要です。

[2] 解法

\(L_i\) の最大値、\(R_i\) の最小値に着目し、それぞれ \(L_l=M,R_r=m\) とします。次のように場合分けをします。

1. \(M \leq m\) のとき

\(M \leq X \leq m\) を満たす整数 \(X\) を \(1\) つ用意します。\(M\) は \(L_i\) の最大値なので、全ての \(i\) について \(L_i \leq X\) です。同様に、全ての \(i\) について \(X \leq R_i\) です。よって、全員を座標 \(X\) に並べることが可能で、不満度は \(0\) です。

2. \(M>m\) のとき

\(M>m\)、すなわち \(L_l>R_r\) なので、\(l \neq r\) です。そこで、\(x_l=A,x_r=B\) としたときの不満度がどのようになるかを考えます。

まず、最適解において全ての \(i\) について \(B \leq x_i \leq A\) であることが示せます。

証明：

最適解において \(x_i < B\) または \(x_i > A\) を満たす \(i\) が存在すると仮定します。\(B \leq m < M \leq A\) なので、すべての \(i\) について \(B \leq R_i\) かつ \(L_i \leq A\) が成り立ちます。よって、\(x_i<B\) を満たす全ての \(i\) について \(x_i=B\) に変更し、\(x_i>A\) を満たす全ての \(i\) について \(x_i=A\) に変更することが可能で、この変更によって不満度は減少します。よって矛盾が示されました。

\(l,r\) のいずれでもない人どうしによる不満度への寄与の総和を \(C\) とすると、不満度は以下のように表されます。

\( \displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}|x_j-x_i| = C + |A-B| +\sum_{i \neq l,r}^{}|x_i-B|+\sum_{i \neq l,r}^{}|A-x_i|\)

\(B \leq x_i \leq A\) を利用して、不満度は以下のように言い換えられます。

\(C + (A-B) \times (N-1)\)

これを最小化するためには、\(A=M,B=m\) とするのが最適です。

\(C\) は再帰的に計算可能で、以上をまとめると最終的な答えは次の式で求められます。

\( \displaystyle\sum_{i=0}^{N-1}\max(0,L_i-R_i)\times(N-2\times i-1)\)

ただし \(L\) は降順に、\(R\) は昇順に、それぞれ並び替えました。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N; cin >> N;
    vector<long long> L(N),R(N);
    for(int i=0;i<N;i++)cin >> L[i] >> R[i];
    sort(L.begin(),L.end(),greater<>());
    sort(R.begin(),R.end());
    long long ans=0;
    for(int i=0;i<N;i++) ans += max(0ll,L[i]-R[i])*(N-2*i-1);
    cout << ans << endl;
}