智障地度过了一个清明节 辣鸡效率。。 来写个blog。。
谢谢某位dalao的指点 问他问题的时候惨遭断句 我：问你个 智障 问题 dalao：对象是“你个智障”？ 我：不不不 我要问您个问题 那是个智障问题 含义是“我是智障”
这道题很多人说不难发现 在排序之后 只会配对相邻前后的2个位置 这是为什么呢 就让本蒟蒻来证一下 首先 可以画个图 你可以自己标一下值什么的 如果有交叉 那么我们交换一下他们 那么交换后的价值是肯定<=之前的代价 可以理解为优于之前的
那么如果有配对到前后3个位置的 （随便画一个） 肯定有3条交叉的线 那肯定是可以交换的 所以就不会有3个的情况 就变成至少两个了
那为什么会有两个的情况 因为题目有相等的限制啊 如果f=c，a=d那就两种调整不能实现 不能变成1个的情况
嗯。。讲完了
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=100010,inf=1e9+7; inline 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<<3)+(x<<1)+ch-'0'; ch=getchar();} return x*f; } int a[N],b[N]; LL f[N]; LL c(LL x,LL y){return x==y?inf:abs(x-y);} int main() { int n=read(),i; for(i=1;i<=n;i++)a[i]=read(),b[i]=read(); if(n==1 && a[1]==b[1]){printf("-1\n"); return 0;} sort(a+1,a+1+n),sort(b+1,b+1+n); f[1]=c(a[1],b[1]),f[2]=min(f[1]+c(a[2],b[2]),c(a[1],b[2])+c(a[2],b[1])); for(i=3;i<=n;i++) { f[i]=f[i-1]+c(a[i],b[i]); f[i]=min(f[i],f[i-2]+c(a[i],b[i-1])+c(a[i-1],b[i])); LL u=min(c(a[i-2],b[i])+c(a[i-1],b[i-1])+c(a[i],b[i-2]), c(a[i-2],b[i-1])+c(a[i-1],b[i])+c(a[i],b[i-2])); u=min(u,c(a[i-2],b[i])+c(a[i-1],b[i-2])+c(a[i],b[i-1])); f[i]=min(f[i],f[i-3]+u); } printf("%lld\n",f[n]); return 0; }