前缀和与差分的笔记"/>
前缀和与差分的笔记
这个题很明显对某一个区间进行加减操作,是一个差分的模版题,只需要注意数据范围,是用int,还是用long long。
#include<iostream>
using namespace std;
int a[5000010];
int sum[5000010];
int n, q, l, r,x;
int main()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];}a[0] = 0;for (int i = 1; i <= n; i++){sum[i] = a[i] - a[i - 1];}for (int i = 1; i <= q; i++){cin >> l >> r >> x;sum[l] += x;sum[r+1] -= x;}for (int i = 1; i <= n; i++){sum[i] += sum[i - 1];}int min = sum[1];for (int i = 1; i <= n; i++){if (min > sum[i]){min = sum[i];}}cout << min;
}
一个简单的前缀和的题只要找到前几项的和=k就输出1如果找不到就输出0;
因为题目中说了是从第i个开始吃不是从头开始,所以只要找到一段连续的子段和为k就行。
#include<iostream>
using namespace std;
using ll = long long;
ll n, k, a[100005],sum[100005];
int main()
{cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}int dex = 0;for (int i = 0; i < n; i++){sum[i] = sum[i - 1] + a[i];}for (int j = 0; j < n; j++){if (sum[j] - sum[j - 1] == k){dex = 1;}}cout << dex << endl;
}
第二个题其实用双指针也可以做同样是进行优化的思路
#include<iostream>
using namespace std;
using ll = long long;
ll n, k, a[100005];int main()
{cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}int left = 0, right = 0;ll sum = 0;int dex = 0;while (right < n){sum += a[right];if (sum == k){dex = 1;break;}while (sum > k){sum -= a[left];left++;}right++;}cout << dex << endl;return 0;
}
双指针其实也是通过限定区间,不断地移动这个区间,来进行判断
- 定义变量n和k,分别表示食物的种类数和连续不停止吃食物的个数。
- 定义数组a,用于存储每种食物的数量。
- 定义变量left和right,分别表示双指针的左右位置,初始值都为0。
- 定义变量sum,用于记录当前窗口内食物的数量之和,初始值为0。
- 定义变量dex,用于记录是否满足条件,初始值为0。
- 使用while循环,不断移动右指针right,并更新sum的值,直到right等于n为止。
- 在每次移动右指针right时,将a[right]的值加到sum中。
- 如果当前窗口内食物的数量之和sum等于k,将dex置为1,并跳出循环。
- 如果当前窗口内食物的数量之和sum大于k,需要移动左指针left,并更新sum的值,直到sum小于等于k为止。
- 在每次移动左指针left时,将a[left]的值从sum中减去。
- 输出dex的值,表示是否满足条件。
总结
前缀和一般是对某几个区间的和进行操作的,这样可以降低直接用暴力相加的复杂度,而差分一般是对某个区间进行加减操作,也是降低复杂度的本质是一种优化
更多推荐
前缀和与差分的笔记
发布评论