[ARC114D] Moving Pieces on Line 解题报告

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=5e3+10;
int n,m,a[N],b[N<<1],c[N<<1],cnt;
ll f[N][N];
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
        b[i]=a[i];
    }
    for(int i=1;i<=m;i++){
        read(b[i+n]);
    }
    m+=n;
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(int i=1,j;i<=m;i=j){
        for(j=i;j<=m;j++){
            if(b[j]!=b[i]){
                break;
            }
        }
        if((j-i)%2){
            c[++cnt]=b[i];
        }
    }
    if(n<cnt){
        puts("-1");
        return 0;
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=cnt;j++){
            if(j)f[i][j]=f[i-1][j-1]+abs(a[i]-c[j]);
            if(i>=2){
                f[i][j]=min(f[i][j],f[i-2][j]+a[i]-a[i-1]);
            }
        }
    }
    write_endl(f[n][cnt]);
    return 0;
}