关于这一题,我的思维是降序排序后,记录两组的和asum和bsum,初始为零,记录两个指针ai,bi初始为1,之后一步步更新答案 1、当两组值相等时,asum+=a[ai],bsum+=b[bi],ai++,bi++同时将抵押加2 2、当asum>bsum,bsum+=b[bi],bi++,将抵押加1 3、当bsum>asum,asum+=a[ai],ai++,将抵押加1 每次用min(aum,bsum)-抵押和答案比较来更新答案 直到ai或bi>n+1 我觉得实质上这个方法与题解是一致的,关于第一步可证明当两边相等时,取一个的结果一定比原来的差,下一步就是取另一个,所以完全可以同时取两个数。。 代码如下 program aaa;
var a,b:array[0..100010] of real; n,i,ai,bi:longint; asum,bsum,sumi,ans:real;
procedure swap(var xa,xb:real); var temp:real; begin temp:=xa; xa:=xb; xb:=temp; end;
procedure qsort1(l,r:longint); var xl,xr:longint; mid:real; begin xl:=l; xr:=r; mid:=a[(l+r) shr 1]; repeat while a[xl]>mid do inc(xl); while a[xr]xr; if xl<r then qsort1(xl,r); if l<xr then qsort1(l,xr); end;
procedure qsort2(l,r:longint); var xl,xr:longint; mid:real; begin xl:=l; xr:=r; mid:=b[(l+r) shr 1]; repeat while b[xl]>mid do inc(xl); while b[xr]xr; if xl<r then qsort2(xl,r); if l<xr then qsort2(l,xr); end;
function min(xa,xb:real):real; begin if xa<xb then exit(xa); end;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do read(b[i]);
qsort1(1,n);
qsort2(1,n);
ans:=0.0;
asum:=0.0;
bsum:=0.0;
sumi:=0.0;
ai:=1;
bi:=1;
while (ai<=n+1) and (bi<=n+1) do
begin
if asum<=bsum then
begin
asum:=asum+a[ai];
inc(ai);
sumi:=sumi+1.0;
end
else
begin
bsum:=bsum+b[bi];
inc(bi);
sumi:=sumi+1.0;
end;
if min(asum,bsum)-sumi>ans then ans:=min(asum,bsum)-sumi; end; write(ans:0:4); end.
但是这份代码怎么都只有5分。。。请教大佬是为什么呢。。