2025年P2367 语文成绩和P5542 Painting The Barn S（一维和二维差分）

大家好，我是讯享网，很高兴认识大家。

前言

一、P2367 语文成绩

二、P5542 Painting The Barn S

前言

图文详解一维差分

图文详解二维差分

一、P2367 语文成绩

题目背景：

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

题目描述：

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

输入格式：

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

第二行有 n 个数，a1 ~ an，代表各个学生的初始成绩。

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

输出格式：

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

样例输入 1：

3 2
1 1 1
1 2 1
2 3 1

讯享网

样例输出 1：

2

说明/提示：

对于 100% 的数据，有 n <= 5 x 10^6，p <= n，学生初始成绩 <= 100，z <= 100。

代码实现：

#include <stdio.h> #define MAX  int a[MAX + 1]; // 不使用下标为 0 的元素 int d[MAX + 2]; // 不使用下标为 0 的元素 int main() { int n = 0, p = 0; scanf("%d %d", &n, &p); int i = 0; // 输入学生的初始成绩 for (i = 1; i <= n; i++) { scanf("%d", &a[i]); } // 初始化差分数组 for (i = 1; i <= n; i++) { d[i] = a[i] - a[i - 1]; } // 对学生的成绩调整 p 次 while (p--) { int x = 0, y = 0, z = 0; scanf("%d %d %d", &x, &y, &z); d[x] += z; d[y + 1] -= z; } // 计算差分数组的前缀和，即原数组 a int min = 101; for (i = 1; i <= n; i++) { a[i] = a[i - 1] + d[i]; if (a[i] < min) min = a[i]; } printf("%d\n", min); return 0; }

讯享网

二、P5542 Painting The Barn S

题目描述：

农夫约翰不擅长多任务处理。他经常分心，很难完成长的项目。目前，他正试图在谷仓的一侧上漆，但他一直在画小矩形区域，然后由于照料奶牛的需要而偏离了方向，使得谷仓的某些部分上漆的涂料比其他部分多。

我们可以将谷仓的一侧描述为一个二维 x-y 平面，农夫约翰在该平面上绘制 n 个矩形，每个矩形的边都与坐标轴平行，每个矩形由谷仓的左下角和右上角点的坐标描述。

农夫约翰想在谷仓上涂几层油漆，这样在不久的将来就不需要再重新粉刷了。但是，他不想浪费时间涂太多的油漆。结果表明，K 涂层是**用量。请在他画完所有的长方形后，帮他确定谷仓有多少面积被 K 层油漆覆盖。

输入格式：

输入的第一行包含 n 和 k（1 ≤ k ≤ n ≤ ）。其余n行中的每一行包含四个整数 x1、y1、x2、y2，描述正在绘制的矩形区域，左下角（x1、y1）和右上角（x2、y2）。所有 x 和 y 值都在 0…1000 范围内，并且所有矩形都有正面积。

输出格式：

请输出谷仓被K层油漆覆盖的区域。

样例输入 1：

3 2
1 1 5 5
4 4 7 6
3 3 8 7

样例输出 1：

8

代码实现：

讯享网#include <stdio.h> int a[1001][1001]; // 不使用下标为 0 的元素 int d[1002][1002]; // 不使用下标为 0 的元素 int main() { int n = 0, k = 0; scanf("%d %d", &n, &k); while (n--) { int x1 = 0, y1 = 0, x2 = 0, y2 = 0; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); x1 = x1 + 1; y1 = y1 + 1; d[x1][y1] += 1; d[x2 + 1][y1] -= 1; d[x1][y2 + 1] -= 1; d[x2 + 1][y2 + 1] += 1; } int cnt = 0; // 计数器 for (int i = 1; i <= 1000; i++) { for (int j = 1; j <= 1000; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j]; if (a[i][j] == k) cnt++; } } printf("%d\n", cnt); return 0; }

2025年P2367 语文成绩和P5542 Painting The Barn S（一维和二维差分）

前言

一、P2367 语文成绩

二、P5542 Painting The Barn S

相关推荐