排序不等式：逆序和>乱序和>顺序和
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long a[100001],b[100001],ans=0,k;
int main()
{
int n;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int i=1,j=n,l=1,r=n;
while(i-1+n-j+1<=k)
{
if(abs(a[i]-b[r])>abs(a[j]-b[l]))
{
ans+=abs(a[i]-b[r]);
i++;r--;
}
else
{
ans+=abs(a[j]-b[l]);
j--;l++;
}
}
cout<<ans;
return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    ll n,t,ans,a[1<<17],b[1<<17],c[1<<17];
    
    int cmp_less(ll x,ll y)
    {
        return x<y;
    }
    int cmp_greater(ll x,ll y)
    {
        return x>y;
    }
    
    void main()
    {
        scanf("%lld%lld",&n,&t);
        for (ll i=0;i<n;i++)
            scanf("%lld",&a[i]);
        for (ll i=0;i<n;i++)
            scanf("%lld",&b[i]);
        sort(&a[0],&a[n],cmp_greater);
        sort(&b[0],&b[n],cmp_less);
        for (ll i=0;i<n;i++)
            c[i]=llabs(a[i]-b[i]);
        sort(&c[0],&c[n],cmp_greater);
        ans=0;
        for (ll i=0;i<t;i++)
            ans+=c[i];
        printf("%lld\n",ans);
    }
}

int main()
{
    dts::main();
}

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
long long a[100005],b[100005],ans;
int n,k,i;
int main()
{
cin>>n>>k;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
cin>>b[i];
}
sort(a,a+n);
sort(b,b+n);
int i1=0;int i2=0;int j1=n-1;int j2=n-1;
while(k)
{
if(abs(a[i1]-b[j1])>abs(a[j2]-b[i2]))
{
ans=ans+abs(a[i1]-b[j1]);
i1++;j1--;
}
else
{
ans=ans+abs(a[j2]-b[i2]);
j2--;i2++;

}
k--;
}
cout<<ans<<endl;
system("pause");
return 0;
}

50AC留念。。。

#include<stdio.h>
int a[100000]={0},b[100000]={0};
void quiksort(int a[],int low,int high)
{
    int i = low;
    int j = high;  
    int temp = a[i]; 
  
    if( low < high)
    {          
        while(i < j) 
        {
            while((a[j] >= temp) && (i < j))
            { 
                j--; 
            }
            a[i] = a[j];
            while((a[i] <= temp) && (i < j))
            {
                i++; 
            }  
            a[j]= a[i];
        }
        a[i] = temp;
        quiksort(a,low,i-1);
        quiksort(a,j+1,high);
    }
    else
    {
        return;
    }
}
int compare(int i,int j)
{
    if(i>j)
        return i-j;
    else return j-i;
}
int main(void)
{
    int n,k,counta1=0,counta2,countb1=0,countb2,i=0;
    unsigned long long sum=0;
    scanf("%d%d",&n,&k);
    counta2=countb2=n-1;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    quiksort(a,0,n-1);
    quiksort(b,0,n-1);
    while(i<k)
    {
        int p,q;
        p=compare(a[counta1],b[countb2]);
        q=compare(a[counta2],b[countb1]);
        if(p>q)
        {
            counta1++;
            countb2--;
            sum+=p;
        }
        else
        {
            counta2--;
            countb1++;
            sum+=q;
        }
        i++;
    }
    printf("%llu",sum);
} 

明明说两个数组不重的，去重只能得十分，不去重却AC了，白提交三次

#include<stdio.h>
void qsort(long a[],long begin_,long end_)
{
long key,temp;
key=a[begin_];
long i=begin_,j=end_;
while(i!=j)
{
while(j!=i)
{
if(a[j]<=key)
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
break;
}
else j--;
}
while(j!=i)
{
if(a[i]>key)
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
break;
}

else i++;

}
}
if(begin_!=i) qsort(a,begin_,i-1);
if(end_!=i) qsort(a,i+1,end_);

}
long A[100000+10],B[100000+10];
int main()
{
long n,k;
scanf("%ld%ld",&n,&k);
for(long i=1;i<=n;i++)
{
scanf("%ld",&A[i]);
}
for(long i=1;i<=n;i++)
{
scanf("%ld",&B[i]);
}
qsort(A,1,n);
qsort(B,1,n);
/*
for(long i=1;i<=n;i++)
{
long pos=i+1;
while(A[i]==A[pos]&&A[i]!=-1&&pos<=n)
{
A[pos]=-1;
pos++;
}
}
for(long i=1;i<=n;i++)
{
long pos=i+1;
while(B[i]==B[pos]&&B[i]!=-1&&pos<=n)
{
B[pos]=-1;
pos++;
}
}
/
long temp1,temp2;
long long sum=0;
long pa1=1,pa2=n,pb1=1,pb2=n;
for(long i=1;i<=k;i++)
{
/
while(A[pa1]==-1)
{
pa1++;
}
while(A[pa2]==-1)
{
pa2--;
}
while(B[pb1]==-1)
{
pb1++;
}
while(B[pb2]==-1)
{
pb2--;
}
*/
temp1=B[pb2]-A[pa1];
temp2=A[pa2]-B[pb1];
if(temp1>temp2)
{
sum=sum+temp1;
pb2--;
pa1++;
}
else
{
sum=sum+temp2;
pa2--;
pb1++;
}
}
printf("%I64d",sum);
}

var
t1,t2,w1,w2,i,j,k,n,m,s,t:longint;
a:array[0..100000,0..1]of longint;
ans:int64;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=a[(l+r) div 2,k];
repeat
while a[i,k]<x do inc(i);while x<a[j,k] do dec(j);
if not(i>j) then
begin
y:=a[i,k];a[i,k]:=a[j,k];a[j,k]:=y;inc(i);j:=j-1;
end;
until i>j;
if l<j then qsort(l,j);if i<r then qsort(i,r);
end;
begin
readln(n,m);
for i:=1 to n do read(a[i,0]);readln;
for i:=1 to n do read(a[i,1]);readln;
k:=0;qsort(1,n);
k:=1;qsort(1,n);
t1:=1;w1:=n;
t2:=n;w2:=1;
for i:=1 to m do
begin
if abs(a[t1,0]-a[w1,1])>abs(a[t2,0]-a[w2,1]) then
begin ans:=ans+abs(a[t1,0]-a[w1,1]);inc(t1);dec(w1); end
else
begin
ans:=ans+abs(a[t2,0]-a[w2,1]);dec(t2);inc(w2);
end;
end;
writeln(ans);
end.

测试数据 #0: Accepted, time = 0 ms, mem = 1392 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1388 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1392 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1388 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1388 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 1388 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 1392 KiB, score = 10
测试数据 #7: Accepted, time = 124 ms, mem = 1388 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 1392 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 1392 KiB, score = 10

简单的贪心。
很容易想到先sort后，然后用头尾指针分别指向a，b两个数组。因为a中最小和b中最大或a中最大和b中最小，肯定是当前最大了，所以只要O(n)的扫一遍，if判断，就能过了。

详细题解和源程序请见：题解

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#define maxn 100001
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int cmp1(const void *a,const void *b){
return *(long )a-(long *)b;
}

int cmp2(const void *a,const void *b){
return -cmp1(a,b);
}
long n,i,j,k,a[maxn],b[maxn];
long long ans=0;
int main(int argc, char *argv[]) {
cin>>n;
cin>>k;
for(i=1;i<=n;i++){
cin>>a[i];
}
for(i=1;i<=n;i++){
cin>>b[i];
}
qsort(a+1,n,sizeof(long),cmp1);
qsort(b+1,n,sizeof(long),cmp2);
i=1;
j=n;
while(k>0){
k--;
if(abs(a[i]-b[i])>abs(a[j]-b[j])){
ans=ans+abs(a[i]-b[i]);
i++;
}
else{
ans=ans+abs(a[j]-b[j]);
j--;

}
}
cout<<ans<<endl;
}

a降序排列
b升序排列
令i=1
j=n
另k--
然后用abs(a[i]-b[i])与abs(a[j]-b[j])相比较
若abs(a[i]-b[i])大 令i++ 和中加上abs(a[i]-b[i]) 然后继续进行，做到k=0为止
若abs(a[j]-b[j])大 令j-- 和中加上abs(a[j]-b[j]) 然后继续进行，做到k=0为止
具体代码不贴了

├ 测试数据 01：答案正确... (0ms, 1584KB)

├ 测试数据 02：答案正确... (0ms, 1584KB)

├ 测试数据 03：答案正确... (0ms, 1584KB)

├ 测试数据 04：答案正确... (0ms, 1584KB)

├ 测试数据 05：答案正确... (0ms, 1584KB)

├ 测试数据 06：答案正确... (0ms, 1584KB)

├ 测试数据 07：答案正确... (0ms, 1584KB)

├ 测试数据 08：答案正确... (0ms, 1584KB)

├ 测试数据 09：答案正确... (0ms, 1584KB)

├ 测试数据 10：答案正确... (0ms, 1584KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 1584KB

快排竟然没有堆栈溢出？100000的规模啊

切记

结果要用int64

我因此WA了一次。

RP不错，随机快排

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

INT64不能读入！`- - 我读了半天的1234

悲剧了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

悲剧啊，如此幼稚的题，考得时候竟然没有加abs~ ~ orz

type

atp = array [1..100000] of longint;

var

a,b : atp;

n , k : longint;

procedure qsort(l,r : longint;var a : atp);

var i , j , temp , mid : longint;

begin

i := l; j := r; mid := a[(l+r) shr 1];

repeat

while a[i] < mid do inc(i);

while a[j] > mid do dec(j);

if i j;

if l < j then qsort(l,j,a);

if i < r then qsort(i,r,a);

end;

procedure init;

var i : longint;

begin

readln(n,k);

for i := 1 to n do read(a[i]); readln; qsort(1,n,a);

for i := 1 to n do read(b[i]); readln; qsort(1,n,b);

end;

procedure main;

var i,ta,ha,tb,hb : longint; ans : int64;

begin

ans := 0; ha := 1; ta := n; hb := 1; tb := n;

for i := 1 to k do

begin

if abs(a[ha] - b[tb]) > abs(a[ta] - b[hb]) then

begin inc(ans,abs(a[ha] - b[tb])); inc(ha); dec(tb); end else

begin inc(ans,abs(a[ta] - b[hb])); inc(hb); dec(ta); end;

end;

writeln(ans);

end;

begin

init;

main;

end.

顶talent123

谢谢！

qsort秒杀。

为什么QSort都这么慢???

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 916ms

├ 测试数据 07：答案正确... 900ms

├ 测试数据 08：答案正确... 884ms

├ 测试数据 09：答案正确... 931ms

├ 测试数据 10：答案正确... 931ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4562ms

Who can tell me why??

program p1662;

var a,b,c:array[1..1000000] of longint;

i,j,k,n:longint;

ans:int64;

procedure qsort(x,y:longint);

var g,t,l,r:longint;

begin

t:=c[(x+y) div 2];l:=x;r:=y;

repeat while c[l]>t do inc(l);

while c[r]

比赛时：ans用longint——50分

然后：ans用int64——AC~

郁闷·~