题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1237
可以贪。
如果没有那个限制两个数组都从小到大扫一遍一一配对就可以了。有那个限制的话可以发现只会有相邻2个或3个可以调整。4个的可以化成1 3或2 2。。
#include<cstring> #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 500500 #define inf 0x7ffffffffffll #define eps 1e-6 #define ll long long ll a[maxn],b[maxn],f[maxn],ans; int n; using namespace std; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } ll p(ll x,ll y){ if (x==y) return inf; else return abs(x-y); } int main(){ n=read(); rep(i,1,n) a[i]=read(),b[i]=read(); sort(a+1,a+1+n); sort(b+1,b+1+n); f[1]=p(a[1],b[1]); f[2]=min(f[1]+p(a[2],b[2]),p(a[1],b[2])+p(a[2],b[1])); rep(i,3,n){ f[i]=min(min(f[i-1]+p(a[i],b[i]),f[i-2]+p(a[i],b[i-1])+p(a[i-1],b[i])), min(f[i-3]+p(a[i-2],b[i])+p(a[i-1],b[i-2])+p(a[i],b[i-1]), f[i-3]+p(a[i],b[i-2])+p(a[i-1],b[i])+p(a[i-2],b[i-1]))); } if (f[n]>inf) puts("-1"); else printf("%lld ",f[n]); return 0; }