CF1765J Hero to Zero 题解

· · 题解

考虑线性规划：

\begin{aligned} \min\ \ \ \sum_i H_i+\sum_j L_j+\sum_{i,j} &P_{i,j}\\ s.t.\ \ \ \ \ \ \forall i,j,H_i+L_j+P_{i,j}&=|a_i-b_j|\\ H_i,L_j\in R,P_{i,j}&\ge 0 \end{aligned}

设约束对偶成变量 y_{i,j}，得到：

\begin{aligned} \max\ \sum_{i,j}|a_i-b_j|&\times y_{i,j}\\ s.t.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ y_{i,j}&\le 1\\ \sum_i y_{i,j}&=1\\ \sum_j y_{i,j}&=1 \end{aligned}

其中两个等式限制由无限制变量 H_i,L_j 得到。

对于对偶后的线性规划，转成二分图，先将所有 y_{i,j} 取到上界，即变成完全图。

对于等式限制就是每个点度数为 1，即对每个点删 n-1 次 边。

将 a,b 排序后考虑二分图性质，显然 若删去的边交叉一定不优 。

于是我们将 (i,i') 边删 n-1 次即可。

code：

#include<bits/stdc++.h>
#define db double
#define int ll
#define ll long long
#define ull unsigned long long
#define pb emplace_back
#define MP make_pair
#define pii pair<int, int>
#define vec vector<int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define CLK (double)clock()/(double)CLOCKS_PER_SEC
using namespace std;
mt19937 rnd(time(0));
inline int read(){
    register int x=0,f=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(register int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int N=2e5+5;
int n,a[N],b[N],suma[N],sumb[N],ans;
void MAIN(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)b[i]=read();sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)suma[i]=suma[i-1]+a[i],sumb[i]=sumb[i-1]+b[i];
    int j=0;
    for(int i=1;i<=n;i++){
        while(j<n&&b[j+1]<a[i])j++;
        ans+=a[i]*j-sumb[j]+(sumb[n]-sumb[j])-a[i]*(n-j);
    }
    for(int i=1;i<=n;i++)ans-=abs(a[i]-b[i])*(n-1);
    cout<<ans;
}
signed main(){
//    freopen("read.in","r",stdin);
//  freopen("write.out","w",stdout);
    int T=1;while(T--)MAIN();
//  printf("\nTIME:%lf\n",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}