UOJ Logo zhangzhiyang的博客

博客

oi赛d1t1的问题

2017-09-04 19:45:59 By zhangzhiyang

关于这一题,我的思维是降序排序后,记录两组的和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分。。。请教大佬是为什么呢。。

评论

暂无评论