9 条题解
-
29
求差分数组中大于0元素的和的程序。它的主要思想是通过计算原序列的差分数组,然后累加差分数组中大于0的元素。
具体解释如下:
- 创建两个数组a和b,长度为100005,用来存储输入数据和差分数组。
- 读入一个整数n,表示序列的长度。
- 通过循环从1到n依次读入序列元素,并计算出差分数组b[i] = a[i] - a[i-1]。
- 初始化变量sum为0,用来存储差分数组中大于0的元素的累加和。
- 再次从1到n的循环中,若差分数组元素b[i]大于0,则将其累加到sum中。
- 输出sum作为结果。
- 程序结束。
这段代码的功能是求取原序列的正增量和(即大于0的差分值的和)。在实际应用中,可以用来统计一段时间内的某种指标的增长总和,比如某种商品的销售额增长等。
#include <bits/stdc++.h> using namespace std; long long a[100005],b[100005], sum; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; //对原序列a,生成它的差分数组b b[i]=a[i]-a[i-1]; } //累加差分数组中,所有大于0的元素 for (int i = 1; i <= n; i++) { if (b[i] > 0) { sum += b[i]; } } cout << sum; return 0; }
-
18
题目大意
存在一个序列a,序列中第i个元素为ai,每次可以将区间[l, r]之间的数都减一,若区间[l, r]之间存在0,就无法对该区间都减一,求最少几次可以将序列中元素都减为0。
完整思路
差分数组进行前缀和操作后,就是原序列,若是要让原序列都为0,那么差分数组也必须都为0。因此对原序列a,生成它的差分数组b,可以得知差分数组b中所有大于0的元素,都是要通过一次次的区间减法操作来去除的,又因为每次区间减法操作只能减一,所以差分数组中大于0的元素之和,就是需要操作的次数。
题解
// 累加差分数组中,所有大于0的元素 for (int i = 1; i <= n; i++) { if (b[i] > 0) { sum += b[i]; } }
- 1
信息
- ID
- 227
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 891
- 已通过
- 567
- 上传者