1 条题解

  • 0
    @ 2023-1-14 11:14:38

    这题其实有一个很巧妙的方法。设一个数组 ddd1d_1 就表示第一个人所得的金币,而 did_i2in2\le i\le n)表示第 ii 个人比第 i1i-1 个人多得的金币。这样,将第到第个人的金币加 cc 只会改变 dd 中的两个值:dada+c,  db+1db+1cd_a\to d_a+c,\ \ d_{b+1}\to d_{b+1}-c。而更重要的是,这样第 ii 个人所得的金币总和其实就是 d1++did_1+\cdots+d_i 的值。

    后记:本文描述的方法叫做差分。可以访问 oi-wiki 获得更多相关内容。

    program Knight;
    
    var
      d:array[1..100008]of longint;
      n,i,j,a,b,c:longint;
    
    begin
      fillchar(d,sizeof(d),0);
    
      readln(n);
      for i:=1 to n+1 do
      begin
        readln(a,b,c);
        d[a]:=d[a]+c;
        d[b+1]:=d[b+1]-c;
      end;
    
      a:=0;
      for i:=1 to n do
      begin
        a:=a+d[i];
        write(a,' ');
      end;
    
      close(input);close(output);
    end.
    
    
    • 1

    信息

    ID
    26
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者