首页 > 代码库 > 配对

配对

描述 Description

   给出2个序列A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]},从A、B中各选出n个元素进行一一配对(可以不按照原来在序列中的顺序),并使得所有配对元素差的绝对值之和最大。

输入格式 InputFormat

输入的第1行为1个整数n
第2行包含n个整数,题目中的A序列。 
第3行包含n个整数,题目中的B序列。 

输出格式 OutputFormat

一个数,最大配对

样例输入:

4
2 5 6 3
1 4 6 7

样例输出:

14


代码

#include <stdio.h>
#include <math.h>
#include <string.h>
int a[10010],b[10010];
void chu(int *s,int n)
{
for(int i=0;i<n;i++)
scanf("%d",&s[i]);
}
void xu(int *s,int n)
{
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
{
int c=s[j]+s[j+1];
s[j]=s[j]<s[j+1]? s[j]:s[j+1];
s[j+1]=c-s[j];
}
}
void dao(int *s,int n)
{
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
{
int c=s[j]+s[j+1];
s[j]=s[j]>s[j+1]? s[j]:s[j+1];
s[j+1]=c-s[j];
}
}
int zui(int *a,int *b,int n)
{
int sum=0;
for(int i=0;i<n;i++)
sum+=fabs(a[i]-b[i]);
return sum;
}
int main(int argc, char *argv[])
{
int n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d",&n);
chu(a,n); chu(b,n);
xu(a,n); dao(b,n);
int zhi=zui(a,b,n);
printf("%d\n",zhi);
return 0;
}

配对