语文成绩

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 \(n\)，\(p\)，代表学生数与增加分数的次数。

第二行有 \(n\) 个数，\(a_1 \sim a_n\)，代表各个学生的初始成绩。

接下来 \(p\) 行，每行有三个数，\(x\)，\(y\)，\(z\)，代表给第 \(x\) 个到第 \(y\) 个学生每人增加 \(z\) 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

样例 #1

样例输入 #1

3 2
1 1 1
1 2 1
2 3 1

样例输出 #1

2

提示

对于 \(40\%\) 的数据，有 \(n \le 10^3\)。

对于 \(60\%\) 的数据，有 \(n \le 10^4\)。

对于 \(80\%\) 的数据，有 \(n \le 10^5\)。

对于 \(100\%\) 的数据，有 \(n \le 5\times 10^6\)，\(p \le n\)，学生初始成绩 $ \le 100\(，\)z \le 100$。

题解

一遍过什么的也太爽了吧？ ˃̶͈ ꇴ ˂̶͈

差分

毕竟是第一次学差分，还是讲一下差分的概念：

对于一个数组arr[ i ]，差分即是diff[ i ] = arr[ i ] - arr[ i - 1 ]。(其中arr[ 0 ] = 0)

依此定义，通过 前缀和 可以将 差分 转换成 原数组。如下。

arr[0] = diff[0] = 0;
arr[1] = diff[1] + diff[0];
arr[2] = diff[2] + diff[1] + diff[0];
arr[3] = diff[3] + diff[2] + diff[1] + diff[0];
arr[4] = diff[4] + diff[3] + diff[2] + diff[1] + diff[0];
... ...

借此，我们可以轻松利用 差分 来批量调节原数组的数据。
例如：将 diff[ 2 ] 增加 2。会有如下效果。(brr[ i ]为新数组)

brr[0] = arr[0]     = diff[0] = 0;
brr[1] = arr[1]     = diff[1] + diff[0];
brr[2] = arr[2] + 2 = diff[2] + 2 diff[1] + diff[0];
brr[3] = arr[3] + 2 = diff[3] + diff[2] + 2 diff[1] + diff[0];
brr[4] = arr[4] + 2 = diff[4] + diff[3] + diff[2] + 2 + diff[1] + diff[0];
... ...

可见原数组从 arr[ 2 ] 这项开始，每项都增加了2。

我们也可以让diff[ 4 ] 减去2，来确保只有arr[ 2 ]和arr[ 3 ]的数据发生变化。

brr[0] = arr[0]     = diff[0] = 0;
brr[1] = arr[1]     = diff[1] + diff[0];
brr[2] = arr[2] + 2 = diff[2] + 2 diff[1] + diff[0];
brr[3] = arr[3] + 2 = diff[3] + diff[2] + 2 diff[1] + diff[0];
brr[4] = arr[4]     = diff[4] - 2 + diff[3] + diff[2] + 2 + diff[1] + diff[0];
brr[5] = arr[5]     = diff[5] + diff[4] - 2 + diff[3] + diff[2] + 2 + diff[1] + diff[0];
... ...

代码

#include <iostream>
using namespace std;

const int MAXN = 5 * 1e6 + 10;

int arr[MAXN], diff[MAXN];
int main()
{
	int n, p;// n为学生数，p为加分次数
	scanf("%d%d", &n, &p);

	// 输入每个学生的初始成绩，并计算差分数组
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &arr[i]);
		diff[i] = arr[i] - arr[i - 1];
	}

	while (p--)
	{
		int x, y, z; //x表示起始学生，y表示结束学生，z表示增加的分数
		scanf("%d%d%d", &x, &y, &z);

		diff[x] += z; // 从第x个学生的成绩开始增加z
		diff[y + 1] -= z;// 从第y+1个学生的成绩开始减少z，确保只对x到y的学生有效
	}

	int min = 100; 
	int tmp = 0;// 临时变量，用来累计当前成绩
	for (int i = 1; i <= n; i++)
	{
		tmp += diff[i];

		// 更新最小成绩
		min = (min < tmp) ? min : tmp;
	}
	printf("%d\n", min);
	return 0;
}