bzoj1237: [SCOI2008]配对
发现排序后匹配的两个点距离不超过2，所以就分情况讨论就行了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll inf=90000000000000000LL; int read() { char ch=getchar();int x=0,f=1; 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; } ll f[100005]; int a[100005],b[100005],n; ll calc(ll x,ll y) { if(x==y) return inf; return abs(x-y); } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(); if(n==1&&a[1]==b[1]) { cout<<"-1"; return 0; } sort(a+1,a+n+1); sort(b+1,b+n+1); f[1]=calc(a[1],b[1]); f[2]=min(f[1]+calc(a[2],b[2]),calc(a[2],b[1])+calc(a[1],b[2])); for(int i=3;i<=n;i++) { f[i]=f[i-1]+calc(a[i],b[i]); f[i]=min(f[i],f[i-2]+calc(a[i-1],b[i])+calc(a[i],b[i-1])); f[i]=min(f[i],f[i-3]+calc(a[i-2],b[i])+calc(a[i-1],b[i-1])+calc(a[i],b[i-2])); f[i]=min(f[i],f[i-3]+calc(a[i-2],b[i-1])+calc(a[i-1],b[i])+calc(a[i],b[i-2])); f[i]=min(f[i],f[i-3]+calc(a[i],b[i-1])+calc(a[i-1],b[i-2])+calc(a[i-2],b[i])); } cout<<f[n]; } |