复兴无基础第三十一课 前缀和与查分
2025-11-23 15:33:22
发布于：上海
2阅读
0回复
0点赞
T1【前缀和与差分】前缀和(强化版)
#include <iostream>
using namespace std;
long long a[1000010], s[1000010];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
//预处理出每个位置的前缀和
s[i] = s[i - 1] + a[i];
}
int l, r;
while (m--) {
cin >> l >> r;
//通过s[r] - s[l - 1]快速求出当前的区间的和
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
T2差分
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){ //差分数组
b[i] = a[i] - a[i - 1];
}
while(m--){ //m次操作
int l, r, c;
cin >> l >> r >> c;
b[l] += c;
b[r + 1] -= c;
}
for(int i = 1; i <= n; i++){ //前缀和
b[i] += b[i - 1];
cout << b[i] << " ";
}
return 0;
}
T3【前缀和与差分】水壶
#include <iostream>
using namespace std;
int a[1000001], sum[1000001];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
// 计算前缀和
sum[i] = a[i] + sum[i - 1];
}
int max = 0;
for (int i = k + 1; i <= n; i++) {
// 求区间内的最大值
int res = sum[i] - sum[i - k - 1];
if (res > max)
max = res;
}
// 输出答案
cout << max;
return 0;
}
T4【前缀和与差分】爱音乐的小码君
#include<iostream>
using namespace std;
int n,m,l,r;
int a[100005],b[100005];
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
//求出从1到i的前缀和
for(int i=1;i<=n;i++){
b[i]=b[i-1]+a[i];
}
cin >> m;
//每一次输出区间和[l,r],也就是[1,r]-[1,l-1]
for(int i=1;i<=m;i++){
cin>>l>>r;
cout<<b[r]-b[l-1]<<endl;
}
return 0;
}
T5【前缀和与差分】语文成绩
#include<iostream>
using namespace std;
//定义两个数组，一个为原数组，一个为差分数组
int n,m,a[5000005],b[5000005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
//将每一次的操作标记在差分数组中
int l,r,c;
while(m--){
cin>>l>>r>>c;
b[l]+=c;
b[r+1]-=c;
}
//差分数组的头标记为0，然后给差分数组做还原操作
b[0]=0;
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
}
//找到成绩最低的同学
int zx=10000000;
for(int i=1;i<=n;i++){
if(a[i]+b[i]<zx) zx=b[i]+a[i];
}
//输出最低的成绩
cout<<zx<<endl;
return 0;
}
T6【前缀和与差分】小码君的荣耀
#include <iostream>
using namespace std;
long long sum[1000005];
int main(){
int n, k;
cin >> n >> k;
//求出前缀和数组
for (int i = 1; i < n; i++){
long long x;
cin >> x;
sum[i] = sum[i - 1] + x;
}
//如果当前传送器传送距离大于终点，直接传送到终点
if (k >= n)cout << 0 << endl;
else {
//找出从什么位置开始使用传送器，路程的花销最短
//定义一个变量ans，ans为在传送半径为 k 的情况下，可以节省的最大的传送时间
long long ans = 0;
for(int i = k; i < n; i++){
ans = max(ans, sum[i] - sum[i - k]);
}
//最后输出最快的时间
cout << sum[n - 1] - ans << endl;
}
return 0;
}
这里空空如也
有帮助，赞一个