如果没有相同的数不能配对的限制
那就是排好序后 Σ abs(ai-bi)
相同的数不能配对
交换一些相邻数的位置，使他们不相同
只交换相邻两个的话：
1 2 3
1 2 3
这种情况不行
而至多相邻3个内部交换，就可以保证相同位置的数不同
#include#include #include using namespace std;typedef long long LL;#define N 100001int a[N],b[N];LL f[N];void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}LL get(int x,int y){ if(x==y) return 1e17; return abs(x-y);}int main(){ int n; read(n); for(int i=1;i<=n;++i) { read(a[i]); read(b[i]); } if(n==1 && a[1]==b[1]) { cout<<-1; return 0; } sort(a+1,a+n+1); sort(b+1,b+n+1); f[0]=0; f[1]=get(a[1],b[1]); f[2]=min(get(a[1],b[1])+get(a[2],b[2]),get(a[1],b[2])+get(a[2],b[1])); for(int i=3;i<=n;++i) { f[i]=f[i-1]+get(a[i],b[i]); f[i]=min(f[i],f[i-2]+get(a[i-1],b[i])+get(a[i],b[i-1])); f[i]=min(f[i],f[i-3]+get(a[i],b[i-1])+get(a[i-1],b[i-2])+get(a[i-2],b[i])); f[i]=min(f[i],f[i-3]+get(a[i],b[i-2])+get(a[i-1],b[i])+get(a[i-2],b[i-1])); f[i]=min(f[i],f[i-3]+get(a[i],b[i-2])+get(a[i-1],b[i-1])+get(a[i-2],b[i])); } cout<
1237: [SCOI2008]配对
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1618 Solved: 633[][][]Description
你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配 对。例如A={5,6,8}，B={5,7,8}，则最优配对方案是5配8, 6配5, 8配7，配对整数 的差的绝对值分别为2, 2, 1，和为5。注意，5配5，6配7，8配8是不允许的，因 为相同的数不许配对。
Input
第一行为一个正整数n，接下来是n 行，每行两个整数Ai和Bi，保证所有 Ai各不相同，Bi也各不相同。
Output
输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输 出-1。
Sample Input
3 3 65 45 10 60 25
Sample Output
32
HINT
1 <= n <= 10^5，Ai和Bi均为1到10^6之间的整数。