【题目来源】
洛谷：P2367 语文成绩 - 洛谷
【题目描述】
语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？
【输入】
第一行有两个整数 \(n\)，\(p\)，代表学生数与增加分数的次数。
第二行有 \(n\) 个数，\(a1∼an\)，代表各个学生的初始成绩。
接下来 \(p\) 行，每行有三个数，\(x\)，\(y\)，\(z\)，代表给第 \(x\) 个到第 \(y\) 个学生每人增加 \(z\) 分。
【输出】
输出仅一行，代表更改分数后，全班的最低分。
【输入样例】
3 2
1 1 1
1 2 1
2 3 1
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P2367 语文成绩》 #差分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, p; // n: 数组长度, p: 操作次数
int a[5000005]; // 原始数组
int b[5000005]; // 差分数组
int minn = 1e9; // 存储最小值，初始化为极大值int main()
{// 输入数组长度和操作次数cin >> n >> p;// 输入原始数组并初始化差分数组for (int i = 1; i <= n; i++) {cin >> a[i];b[i] = a[i] - a[i - 1]; // 计算差分数组}// 处理每个区间增加操作while (p--) {int x, y, z;cin >> x >> y >> z;// 差分数组实现区间增加b[x] += z; // 区间起点增加zb[y + 1] -= z; // 区间终点+1位置减少z}// 通过差分数组还原最终数组for (int i = 1; i <= n; i++) {b[i] = b[i - 1] + b[i]; // 计算前缀和得到最终值}// 寻找数组中的最小值for (int i = 1; i <= n; i++) {minn = min(minn, b[i]); // 更新最小值}// 输出最小值cout << minn << endl;return 0;
}
【运行结果】
3 2
1 1 1
1 2 1
2 3 1
2