C - Min Diff Sum Editorial by blackyuki
[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;
}
posted:
last update: