信奥赛-刷题笔记-差分篇-T2-P2367语文成绩0526

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

差分篇题单

P2367 语文成绩

https://www.luogu.com.cn/problem/P2367

题目背景

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

题目描述

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

输入格式

第一行有两个整数 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 。

代码1-暴力

#include<bits/stdc++.h>

using namespace std;

const int maxn=5e6+10;
int n,p;// n个人 p次修改
int x,y,fen;//x到y 修改fen 
int arr[maxn];
 
int main(){
	// 语文成绩
	// 输入
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	} 
	// 进行p次操作
	for(int i=1;i<=p;i++){
		cin>>x>>y>>fen;
		// x y 1 给x-y中的每个人加 1分
		for(int j=x;j<=y;j++){
			arr[j]+=fen; 
		} 
		
	} 
	int temp=arr[1];
	for(int i=1;i<=n;i++){
		if(temp>arr[i]) temp=arr[i];
	} 
	cout<<temp;
	
	
	return 0;
} 

代码2-差分

当然可以！你提供的这段代码使用了差分数组（Difference Array）技术，非常高效地解决了这个问题。我们来详细解释一下这个算法的原理、实现过程以及为什么它适合处理“区间批量修改 + 最终查询”的问题。

🧠 题目简述

输入：

• 学生人数 n 和操作次数 p
• 初始成绩数组 a[1..n]
• 接下来 p 次操作：每次给第 x 个到第 y 个学生每人加 z 分

输出：

• 修改后所有学生的最低分数

⚙️ 技术背景：差分数组（Difference Array）

原理：

差分数组 d[i] 定义为：

d[i] = a[i] - a[i-1]

我们可以用差分数组快速进行 区间加法操作，而不需要遍历整个区间。

区间操作技巧：

如果我们想对 a[x ... y] 的每个元素都加上 z，只需在差分数组中做以下两步操作：

d[x] += z;
d[y+1] -= z;

这样，当我们最后还原数组时，就相当于对 a[x...y] 所有数加了 z。

✅ 优点总结：

🔍 代码逐行解析

#include<bits/stdc++.h>
using namespace std;

int d[5000001]; // 差分数组
int a[5000001]; // 原始数组

int main()
{
    int n, p, x, y, z, i, min=1e9; // 初始化最小值为一个很大的数

    cin >> n >> p; // 输入学生数量和操作次数

    // 读取初始成绩数组
    for(i=1; i<=n; i++)
    {
        cin >> a[i];
    }

    // 构建差分数组
    for(i=1; i<=n; i++)
    {
        d[i] = a[i] - a[i-1]; // 差分数组定义
    }

    // 处理每一次加分操作
    for(i=0; i < p; i++)
    {
        cin >> x >> y >> z;
        d[x] += z;      // 在起始位置增加 z
        d[y+1] -= z;    // 在结束位置后一位减去 z
    }

    // 还原原始数组并找出最小值
    for(i=1; i <= n; i++)
    {
        a[i] = a[i-1] + d[i]; // 从差分数组恢复 a[i]
        if(min > a[i])
        {
            min = a[i]; // 更新最小值
        }
    }

    cout << min; // 输出最终的最低分

    return 0;
}

📊 示例演示（以样例输入为例）

输入：

3 2
1 1 1
1 2 1
2 3 1

步骤分析：

1. 初始 a = [0, 1, 1, 1] （注意我们是从 i=1 开始存储）
2. 构造差分数组：d[1] = 1 - 0 = 1 d[2] = 1 - 1 = 0 d[3] = 1 - 1 = 0
3. 第一次操作：x=1, y=2, z=1d[1] += 1 → d[1] = 2 d[3] -= 1 → d[3] = -1
4. 第二次操作：x=2, y=3, z=1d[2] += 1 → d[2] = 1 d[4] -= 1 → d[4] = -1 (越界不影响)
5. 还原数组：a[1] = a[0] + d[1] = 0 + 2 = 2 a[2] = a[1] + d[2] = 2 + 1 = 3 a[3] = a[2] + d[3] = 3 + (-1) = 2
6. 最小值是 min(2, 3, 2) = 2

✅ 输出正确！

🧪 性能分析

对于 n = 5e6，这是完全可以在时间限制内完成的。

📌 小结

✅ 本题关键点：

• 使用差分数组代替暴力遍历区间，大大提升效率
• 差分数组适用于“区间加法”+“最终求值”的场景
• 只需两次数组遍历即可完成整个任务

❗ 注意事项：

• 数组要从 i=1 开始，避免边界混乱
• d[y+1] -= z 中 y+1 要小于等于数组长度（否则无效但不会报错）
• 最小值初始化要用一个足够大的值（如 1e9）

如果你还想看看怎么把这个方法扩展到支持“单点更新”、“多次查询”或者“在线维护最值”，欢迎继续问我 😊

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;
 
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	cout<<"Hello NOI"<<endl;
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    freopen("7532.in", "r", stdin);
    freopen("7532.out", "w", stdout);
    //原来的代码保持不变
    double a, b, r;
    int k;
    cin >> a >> b;
    k = int(a/b);
    r = a - b * k;
    printf("%g", r);
    //-------------
    fclose(stdin);
    fclose(stdout);
    return 0;
}