话说有些重要的细节需要注意,比如标准差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;