5016

· · 题解

这道题Pascal写的人很少,所以我来写一下。比较简单易懂,主要看后面的提示和数据范围(important)。Pascal的朋友们嗨起来(呜呜呜,CSP将不能使用Pascal语言了)

第一步,和提示一样,先去计算原先双方实力如何。

a[p1]:=s1+a[p1];//因为天降神兵,所以要在p1的兵营增加s1个兵。
  for i:=1 to n do
    begin
      if i<m then
        l:=l+a[i]*(m-i);//龙方
      if i>m then
        h:=h+a[i]*(i-m);//虎方
    end;

第二步,我们要分三种情况,龙小于虎,龙等于虎,龙大于虎。分类讨论,其中有一个地方注意点,我会在最后讲。

if l<h then
    begin
      for i:=1 to m-1 do//要在m前面的兵营用i去枚举。
        begin
          if abs(l+s2*(m-i)-h)<min then//判断双方差值是不是更小
            begin
              min:=abs(l+s2*(m-i)-h);//更新min
              p2:=i;//记录兵营
            end;
        end;
      //此处缺少
    end;```
  if l=h then
    begin
      write(m);//双方相同时,则放在m处最佳。
      halt;//结束程序。
    end;
  if l>h then//(和上面类似)
    begin
      for i:=m+1 to n do//从m+1处开始枚举
        begin
          if abs(h+s2*(i-m)-l)<min then
            begin
              min:=abs(h+s2*(i-m)-l);//更新
              p2:=i;
            end;
        end;
      //此处缺少
    end;

这是我刚开始的一种方法,最后这样只能拿76分(数据范围完全)。所以程序中有漏洞。往下看↓

因为龙方和虎方实力不相等时,没有枚举到m兵营。所以可能出现第二次神兵放在m号兵营会比放在低实力的一方min值更小。我 们可以采取循环后判断,或者可以直接将循环接触到m兵营。

if abs(h-l)<min then//假如双方实力相减会比上面的枚举还要小,那么更新。
        begin
          min:=abs(h-l);
          p2:=m;
        end;

以上是以l<h为例的。

第三步,检查范围。

想要拿到100分,数据范围扩大很快,我们注意一点,min值必须在int64范围内了,假如你设置min初值是maxlongint,那就不行了,必须要设置到int64的最大范围。min值建议设置成8888888888888888888(19个8).此外,在注意一下其他变量的范围,你就AC了。

下面公布完整代码。(掌声在哪里?)

var n,i,m,p1,p2,s1,s2:longint; l,h,min:int64;
    a:array[1..100000] of int64;
begin
  read(n); min:=888888888888888888;
  for i:=1 to n do read(a[i]);
  read(m,p1,s1,s2);
  a[p1]:=s1+a[p1];
  for i:=1 to n do
    begin
      if i<m then
        l:=l+a[i]*(m-i);
      if i>m then
        h:=h+a[i]*(i-m);
    end;
  if l<h then
    begin
      for i:=1 to m-1 do
        begin
          if abs(l+s2*(m-i)-h)<min then
            begin
              min:=abs(l+s2*(m-i)-h);
              p2:=i;
            end;
        end;
      if abs(h-l)<min then
        begin
          min:=abs(h-l);
          p2:=m;
        end;
    end;
  if l=h then
    begin
      write(m);
      halt;
    end;
  if l>h then
    begin
      for i:=m+1 to n do
        begin
          if abs(h+s2*(i-m)-l)<min then
            begin
              min:=abs(h+s2*(i-m)-l);
              p2:=i;
            end;
        end;
      if abs(h-l)<min then
        begin
          min:=abs(h-l);
          p2:=m;
        end;
    end;
  write(p2);
end.

谢谢大家,这是我第一次写普及组的题解,支持一下我和Pascal。