22软工孟姿好

用户名：dotcpp0669285

访问量：658

签　名：

莫道桑榆晚，为霞尚满天

等　　级
排　　名	1063
经　　验	3261
参赛次数	12
文章发表	39
年　　龄	20
在职情况	学生
学　　校	bilibili大学
专　　业	软件工程

　　自我简介：

自强不息

TA的其他文章

旧物有情 # 枚举法求素数
浏览：17

旧物有情 # 枚举法求水仙花数
浏览：13

旧物有情 # 遍历求二维数组转置
浏览：8

你可能喜欢

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

1501: 蓝桥杯算法提高VIP-分苹果

　　作者: 22软工孟姿好　　　　发表时间：2024-10-25 09:07:20 浏览：10　|　评论：0　

原题链接：蓝桥杯算法提高VIP-分苹果

这道题考察前缀和 , 差分

- 前缀和数组 : 定义一个数组 , 该数组 记录了 数列的前x个值的和

- 例如 数列 1 2 3 4 5,前缀和数组为a[N]
  那么a[1]=1,a[2]=1+2,a[3]=1+2+3......a[5]=1+2+3+4+5
  如果要求[2,3]区间的和,就可以用 a[3]-a[1],在O(1)时间复杂度求出数列中任意的和

- 什么是差分?差分就是前缀和的逆运算
  给定原数组 A[1,2,3,4,5]
  构造差分数组B,使得A成为B的前缀和数组

- 用处 : O(1)时间复杂度在指定区间内进行数字的加减
  例如在区间[2,4]这个范围内统一加上一个数字C

```c++
  void insert(int l,int r,int c){
  	b[l] +=c;
  	b[r+1]-=c;
  }
  ```

我们只需要在左端点加上C,在右端点+1的位置减去C,利用对差分数组进行求前缀和,就可以让指定区间内进行加减某个数

**差分数组的构造**

```c++
//假设最开始数组A[N]是空的,那么其的差分数组一定也是空的
//往数组A[N]中录入数字的过程中,看成了进行n步的加入C的操作
//第一次在 1,1这个范围上加入a[1]
//第二次在 2 2 这个范围上加入a[2]
void insert(int l,int r,int c){
	b[l] +=c;
	b[r+l]-=c;
}
```

**核心: `将a[L~R]全部加上C 等价于 b[L]+=C,b[L+1]-=C`**

```c++
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

void insert(int l, int r, int c) {
	b[l] += c;
	b[r + 1] -= c;
}

int main() {
	int n, m;
	cin >> n >> m;
	
	//最开始的数组
	for (int i = 1; i <= 5; i++)a[i] = 0;

//进行 m 次操作,每次加上c
	for (int i = 1; i <= m; i++) {
		int l, r, c;
		cin >> l >> r >> c;
		insert(l, r, c);
	}

//对差分数组求和
	for (int i = 1; i <= n; i++)a[i] = a[i - 1] + b[i];

for (int i = 1; i <= n; i++)cout << a[i] << " ";

return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

22软工孟姿好

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

1501: 蓝桥杯算法提高VIP-分苹果

评论区

精彩推荐

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

筛排处理（C语言代码）

简单的a+b （C语言代码）

C二级辅导-温度转换（C语言代码）

22软工孟姿好

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-进制转换 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

1501: 蓝桥杯算法提高VIP-分苹果

评论区

精彩推荐

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

筛排处理 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-温度转换 （C语言代码）

字符逆序（C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

筛排处理（C语言代码）

C二级辅导-温度转换（C语言代码）