1 条题解
-
0
这题其实有一个很巧妙的方法。设一个数组 , 就表示第一个人所得的金币,而 ()表示第 个人比第 个人多得的金币。这样,将第到第个人的金币加 只会改变 中的两个值:。而更重要的是,这样第 个人所得的金币总和其实就是 的值。
后记:本文描述的方法叫做差分。可以访问 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
- 上传者