# 56 条题解

• @ 2017-07-27 11:24:28

排序不等式：逆序和>乱序和>顺序和
#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;
}

• @ 2020-11-14 18:11:11
``````#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();
}
``````
• @ 2017-03-18 10:46:49

#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;
}

• @ 2017-02-04 13:12:53

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);
}
``````
• @ 2016-08-02 19:10:20

明明说两个数组不重的，去重只能得十分，不去重却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);
}

• @ 2015-03-08 13:28:54

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
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.

• @ 2014-07-13 15:06:46

测试数据 #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

• @ 2013-12-07 16:39:22

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

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

• @ 2013-09-05 20:34:45

#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;
}

• @ 2013-09-05 20:22:14

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为止
具体代码不贴了

• @ 2012-11-04 13:53:34

├ 测试数据 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的规模啊

• @ 2016-11-12 18:42:30

快速排序基于二分，100000的话总共递归20左右，就是用埃尼阿克运行都不会爆栈啊。。

• @ 2010-04-08 22:57:02

切记

结果要用int64

我因此WA了一次。

• @ 2009-11-10 15:48:27

RP不错，随机快排

• @ 2009-10-12 21:57:36

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-10-07 13:01:09

悲剧了。

• @ 2009-10-06 15:09:02

编译通过...

├ 测试数据 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

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.

• @ 2009-10-05 15:05:34

顶talent123

谢谢！

qsort秒杀。

• @ 2009-10-05 09:50:22

为什么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??

• @ 2009-10-04 21:13:11

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]

• @ 2009-10-04 13:35:29

比赛时：ans用longint——50分

然后：ans用int64——AC~

郁闷·~

ID
1662

4

(无)

2302

942

41%

2