ZX1023 语文成绩
大约 1 分钟
ZX1023 语文成绩
【算法】 差分
【C++】 差分数组、一维数组
【难度】 普及−
一、题目简述
个学生(),初始成绩 。 次操作,每次给区间 每人加 分。 次操作后,求全班最低分。
二、解题思路
,如果每次操作都循环加, 会超时。需要用差分数组:
diff[i] = a[i] - a[i-1](差分数组)- 区间加 加 :
diff[x] += z; diff[y+1] -= z - 所有操作完后,前缀和还原:
a[i] = a[i-1] + diff[i] - 遍历找最小值
手动模拟:初始 [1,1,1],操作 [1,2]+1,[2,3]+1
- diff:
[1,0,0,0] - 操作1: diff[1]+=1, diff[3]-=1 →
[2,0,-1,0] - 操作2: diff[2]+=1, diff[4]-=1 →
[2,1,-1,-1] - 还原:a[1]=2, a[2]=3, a[3]=2。最低=2 ✅
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int diff[N];
int main() {
int n, p;
scanf("%d%d", &n, &p);
int prev = 0;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
diff[i] = x - prev; // 构建差分
prev = x;
}
while (p--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
diff[x] += z;
diff[y + 1] -= z;
}
int cur = 0, ans = 2e9;
for (int i = 1; i <= n; i++) {
cur += diff[i]; // 前缀和还原
ans = min(ans, cur);
}
printf("%d\n", ans);
return 0;
}四、复杂度分析
- 时间:
- 空间:
