讨论 / 我发一个总结吧
zlfp 2012-07-29 01:36:00
点我顶贴 收藏 删除
拿到这道题的时候看到数据范围大概可以想到复杂度是在O(nlogn)一下的,细读题目发现可以二分。那么二分部分O(logn)好写,然后考虑检验值的计算,必须要在O(n)时间内求出。直接模拟的话要O(nm)会爆。不难想到经典的前缀和,用O(n)时间预处理,然后O(1)得出检验值,O(n)+O(1)=O(n),总复杂度为O(nlogn) 圆满解决了。

话说有些重要的细节需要注意,比如标准差s题目没有给范围,但却要用int64;还有二分时的边界值得注意。

关键代码如下:

function get(ww:longint):int64;

var i:longint;

begin

sum[0]:=0;vsum[0]:=0;

for i:=1 to n do

begin

if w[i]>=ww then

begin

sum[i]:=sum[i-1]+1;

vsum[i]:=vsum[i-1]+v[i];

end else

begin

sum[i]:=sum[i-1];

vsum[i]:=vsum[i-1];

end;

end;

get:=0;

for i:=1 to m do

inc(get,(sum[r[i]]-sum[l[i]-1])*(vsum[r[i]]-vsum[l[i]-1]));

end;

procedure main;

var temp,temp2,ans:int64;

ll,rr,mid,count:longint;

begin

ll:=wmin;rr:=wmax+1;

count:=0;ans:=abs(s-get(wmax));

repeat

mid:=(ll+rr)shr 1;

temp:=get(mid);

temp2:=abs(s-temp);

if temp2<ans then

begin

ans:=temp2;

count:=0;

end else inc(count);

if s-temp=0 then

begin

writeln(0);

halt;

end;

if s-temp>0 then rr:=mid else ll:=mid;

until (abs(ll-rr)=1)or(count=10000);

writeln(ans);

end;

查看更多回复
提交回复