2361. 期中考试成绩调整
1000ms
256MB
简单
前缀和与差分
题目描述
某校期中考试结束后采用阅卷机阅卷。老师在检查成绩时发现阅卷机阅卷有误，因此需要手动调整同学们的成绩。
现有 $n$ 个同学的初始成绩，需要进行 $p$ 次调整。每次调整操作将第 $x$ 个同学到第 $y$ 个同学（包含第 $x$ 个和第 $y$ 个同学）的成绩每人加上 $z$ 分。
请问在所有调整操作完成后，全班同学的最低分是多少？
输入格式
- 第一行包含两个正整数 $n$ 和 $p$ ($1 \le n \le 100000, \quad 1 \le p \le n$)，分别代表学生人数和增加分数的次数。
- 第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 100$)，代表每个学生的初始成绩。
- 接下来 $p$ 行，每行包含三个整数 $x, y, z$ ($1 \le x \le y \le n, \quad 0 \le z \le 100$)，代表给第 $x$ 个同学到第 $y$ 个同学每人增加 $z$ 分。
输出格式
- 输出一行一个整数，代表修改分数后全班的最低分。
样例 1
输入 (Input)
3 2 1 1 1 1 2 1 2 3 1
输出 (Output)
2
- 对于 $100\%$ 的数据：$n \le 100000$，$p \le n$，$1 \le x \le y \le n$，$0 \le a_i, z \le 100$。
- **算法提示**：
若对每次区间修改都直接遍历修改数组中的元素，单次修改的复杂度为 $O(N)$，总时间复杂度为 $O(N \cdot P)$，在最大数据范围下会超时（TLE）。
本题需要使用**差分数组**优化区间修改：
1. 设差分数组为 $D$，初始时令 $D[i] = a[i] - a[i-1]$。
2. 对于每次区间修改操作，将区间 $[x, y]$ 内的每个数加上 $z$，只需将差分数组进行如下操作：
- $D[x] \leftarrow D[x] + z$
- $D[y+1] \leftarrow D[y+1] - z$
3. 所有修改操作完成后，通过求差分数组的前缀和（$a[i] = a[i-1] + D[i]$）还原出修改后的最终成绩数组，并遍历寻找最小值。
4. 这种方法使单次修改的时间复杂度降低至 $O(1)$，整体时间复杂度为 $O(N + P)$，能够高效地在时限内运行完毕。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功