|
1、差分
? 就目前本菜鸟觉得，使用差分的情况一般是这样的：
? ? ? ? 现有n个数字，需要对其进行m次操作。每次操作都会将第l个数到第r个数加上整数k。进行完所有的m次操作以后，按次序输出这n个数字。
? ? ? ? 因为，会进行m次操作，所以如果每次加k都遍历一次数组，代码所需要的时间就会很长。也就是说，很容易超时。于是为了解决这个问题，我们就应该拿出我们的“法宝”——差分啦！
? ? ? ? 我们将这n个数放入数组a（后面的数组，大部分都会因为我过于懒而简写哈），然后我们再定义一个数字b，达到下面这样的效果：
| a[1]? = b[1] | | a[2] = b[1] + b[2] | | ...... | | a[i] = b[1] + b[2] +...b[i] |
? ? ? ? 也就是说：
| b[1] = a[1] - a[0] | | b[2] = a[2] - a[1] | | ...... | | b[i] = a[i] - a[i-1] |
? ? ? ? 所以，当需要将第l个数到第r个数都加k的时候，只需要将b[l] + k，然后将b[r+1] - k。这样反复按题目意思操作完m次以后，在将求出a数组中的数，并且按次序输出。就解决了多次遍历数组带来的麻烦问题。
? ? ? ? 而为了减少代码的运行时间，我们是可以在一边输入a数组的时候，一边求b数组相对应的值。具体操作请参照示例代码。（至于为什么不使用c++的标准输入输出格式，请往后翻）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[10000010] , b[10000010];
int main () {
ll N , M;
ll l , r , k;
scanf("%lld %lld",&N,&M);
for(ll i = 1 ; i <= N ; i ++) {
scanf("%lld",&a[i]);
b[i] = a[i] - a[i-1];
}
for(ll i = 0 ; i < M ; i ++){
scanf("%lld %lld %lld",&l,&r,&k);
b[l] += k;
if(r+1 <= N)b[r+1] -= k;
}
for(ll i = 1 ; i <= N ; i ++){
a[i] = b[i] + a[i-1];
printf("%lld ",a[i]);
}
return 0;
}
2、scanf和cin输入时间上的区别（同样适用于printf和cout）
? ? ? ? 首先，相信小伙伴们都知道的。scanf是c语言的标准输入格式，而cin是c++的标准输入格式。很多小伙伴们学了c语言以后，又开始学c++，就会觉得很舒服吧（反正，这是我本人，哈哈）。
? ? ? ? 而众多舒服的点之中，有一个就是使用cin输入，不需要指明输入的究竟是整型数，浮点数还是字符等等。
? ? ? ? 所以，所以，舒服是舒服了，这代码的运行时间它可就上去了。
? ? ? ? cin输入会比scanf输入使用的时间长三四倍左右，因为我们使用cin时，没有标明数据的类型，所以，输入之后cin还会花费时间判断我们输入的数据类型。而使用scanf时，我们会标明数据类型，比如%d,%lld,%s等等，就节省了很多时间。
? ? ? ? 所以，在做那些严格卡时间的题目时，使用scanf和printf，比较cin和cout就更加保险的哇。
|