信奥赛-刷题笔记-前缀和篇-T2-P6568[NOI Online #3 提高组] 水壶0523
原创
信奥赛-刷题笔记-前缀和篇-T2-P6568[NOI Online #3 提高组] 水壶0523
原创
总题单
本部分总题单如下
【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)
https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2
前缀和篇题单
P6568 NOI Online #3 提高组 水壶
题目描述
有 n 个容量无穷大的水壶，它们从 1\sim n 编号，初始时 i 号水壶中装有 A_i 单位的水。
你可以进行不超过 k 次操作，每次操作需要选择一个满足 1\le x\le n-1 的编号 x ，然后把 x 号水壶中的水全部倒入 x+1 号水壶中。
最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。
输入格式
第一行一个正整数 n ，表示水壶的个数。
第二行一个非负整数 k ，表示操作次数上限。
第三行 n 个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量 A_1 , A_2 , \cdots , A_n 。
输出格式
一行，仅一个非负整数，表示答案。
输入输出样例 #1
输入 #1
10
5
890 965 256 419 296 987 45 676 976 742输出 #1
3813说明/提示
数据规模与约定
- 对于 10\% 的数据，保证 n \leq 10 。
- 对于 30\% 的数据，保证 n \leq 100 。
- 对于 50\% 的数据，保证 n \leq 10^3 。
- 对于 70\% 的数据，保证 n \leq 10^5 。
- 对于 100\% 的数据，保证 1\leq n\leq 10^6 ，0\leq k \leq n-1 ，0\le A_i\le 10^3 。
代码1-贪心模拟-是错误的答案啊
#include<bits/stdc++.h>
using namespace std;
int n,k,sh[1000010];
int main(){
// 输入水壶初始值
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>sh[i];
}
// for(int i=1;i<=n;i++){
// cout<<sh[i]<<" ";
// }
// 每次找出连续两个和最大的值，累加起来
for(int i=1;i<=k;i++){
int temp=-1;
int x1,x2;
// 找出一个最合适的操作 ，即当前的值与下一个值的和最大
for(int j=1;j<=n-1;j++){
if(temp<sh[j]+sh[j+1]){
temp=sh[j]+sh[j+1];
x1=j,x2=j+1;
}
}
// 找到最合适的下表后，累加修改水壶数组
sh[x2] += sh[x1];
sh[x1] = 0;
}
int temp=-1;
// 输出最大值
for(int i=1;i<=n;i++){
if(temp<sh[i]) temp=sh[i];
}
cout<<temp;
return 0;
}你的代码思路是：每次操作选择相邻两个水壶，把前一个倒入后一个中，然后重复这个贪心策略 $k$ 次。最后取最大值作为答案。
乍一看似乎合理，但其实 贪心策略并不总是最优的。我们来详细分析你为什么错了。
🚫 你的做法的问题
1. 贪心局部最优 ≠ 全局最优
你每一步都试图选择当前相邻两个数之和最大的位置进行合并，以为这样最终能得到最大值。
但问题在于：
- 合并顺序会影响后续的选择。
- 某些“暂时看起来小”的合并，可能在后面带来更大的收益。
✅ 示例说明：
比如：
n = 3
k = 2
A = [1, 100, 1]如果你第一次选 (1+100)，变成 0,101,1，第二次选 (101+1)，得到 0,0,102，最终结果是 102。
✅ 正确做法是可行的。
但如果数据是：
n = 4
k = 2
A = [1, 99, 100, 1]你第一步可能会合并 99+100=199，变成 1, 0, 199, 1
第二步合并 199+1=200，最终最大是 200。
但是如果我们先合并 1+99=100，变成 0, 100, 100, 1，再合并 100+100=200，也能达到 200。
所以这组数据没问题。
❌ 然而下面这个例子会直接击溃你的贪心逻辑：
n = 5
k = 2
A = [100, 1, 1, 1, 100]你第一次会合并中间的 1+1=2，变成 100,1,0,2,100
第二次合并 2+100=102，变成 100,1,0,0,102，最终最大是 102。
但实际上，我们可以这样做：
- 合并第一个 100 → 得到 0,101,1,1,100
- 再合并 101 → 得到 0,0,102,1,100
最大是 102。
✅ 但还有更优解法吗？
当然有！
更优路径：
- 合并第四个 1 → 第五个 100（即右边）100,1,1,0,101
- 合并第二个 1 → 第三个 1（左边）100,0,2,0,101 → 最终最大是 101 和 100，不如前面。
那如果我们从两端往中间推呢？
最优解：
- 合并第一个 100 → 第二个 1：0,101,1,1,100
- 合并第五个 100 → 第四个 1：0,101,1,101,0 → 最终最大值为 101 + 1 = 102
结论：无论怎么组合，最多只能做到 102。
但是注意：
如果你的贪心每次都选当前最大和的位置，就有可能错过某些全局更优的合并路径。
代码2-前缀和
使用前缀和的方法可以有效地解决这个问题。前缀和数组可以帮助我们快速计算任意子数组的和，从而在常数时间内完成子数组和的计算。以下是使用前缀和方法来实现该题目的完整代码，并附有详细注释。
使用前缀和的方法
- 构建前缀和数组：
prefix_sum[i]表示从第一个水壶到第i个水壶的总水量。 - 计算子数组和：对于长度为
k+1的子数组[j, j+k]，其和可以通过prefix_sum[j+k+1] - prefix_sum[j]快速得到。 - 遍历所有可能的子数组：寻找最大值。
完整代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
long long A[MAXN], prefix_sum[MAXN];
int main() {
int n, k;
cin >> n >> k; // 输入水壶数量n和最多操作次数k
// 初始化前缀和数组
prefix_sum[0] = 0;
// 读取每个水壶的初始水量并构建前缀和数组
for (int i = 1; i <= n; ++i) {
cin >> A[i];
prefix_sum[i] = prefix_sum[i - 1] + A[i];
}
/*
* 示例输入：
* 10
* 5
* 890 965 256 419 296 987 45 676 976 742
*/
long long max_sum = 0;
// 遍历所有可能的长度为 k+1 的子数组，找到其中的最大和
for (int i = 0; i + k + 1 <= n; ++i) {
long long current_sum = prefix_sum[i + k + 1] - prefix_sum[i];
if (current_sum > max_sum) {
max_sum = current_sum;
}
}
// 输出最终能够喝到的最大水量
cout << max_sum << endl;
return 0;
}程序将执行以下步骤：
- 构建前缀和数组：prefix_sum = [0, 890, 1855, 2111, 2530, 2826, 3813, 3858, 4534, 5510, 6252]
- 遍历所有可能的长度为
k+1=6的子数组，计算它们的和，并更新最大值：- 子数组
[1, 6]的和：prefix_sum[6] - prefix_sum[0] = 3813 - 0 = 3813 - 子数组
[2, 7]的和：prefix_sum[7] - prefix_sum[1] = 3858 - 890 = 2968 - ...
- 最终最大值为
3813
- 子数组
因此，输出结果为 3813。
这种方法的时间复杂度为 O(n)，因为我们只需遍历数组两次（一次构建前缀和数组，一次遍历查找最大子数组和）。空间复杂度也是 O(n)，用于存储前缀和数组。
代码3-双指针
双指针方法解析
双指针方法非常适合解决这类需要遍历数组并计算子数组和的问题。其核心思想是通过两个指针（窗口的左右边界）来维护一个动态的窗口，并随着指针的移动更新窗口内的元素总和。
算法思想：
- 初始化：定义两个指针
left和right，分别表示当前窗口的左边界和右边界。 - 滑动窗口：
- 开始时，
left和right都指向数组的第一个元素。 - 每次将
right向右移动一格，同时增加窗口内的元素总和。 - 当窗口大小超过
k+1时，将left向右移动一格，同时减少窗口内移除的元素值。
- 开始时，
- 更新最大值：在每次调整完窗口后，检查当前窗口内的元素总和是否为最大值。
- 终止条件：当
right到达数组末尾时，算法结束。
这种方法可以确保我们以线性时间复杂度 O(n) 完成任务，因为每个元素只会被访问两次（一次由 right 指针访问，一次由 left 指针访问）。
双指针实现代码
以下是基于上述思想的完整代码实现，并附有详细注释。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int A[MAXN]; // 存储每个水壶初始水量
int main() {
int n, k;
cin >> n >> k; // 输入水壶数量n和最多操作次数k
// 读取每个水壶的初始水量
for (int i = 1; i <= n; ++i) {
cin >> A[i];
}
long long sum = 0; // 当前窗口内的水量总和
int left = 1, right = 1; // 初始化双指针
long long max_sum = 0; // 记录最大水量
while (right <= n) {
// 将当前元素加入窗口
sum += A[right];
// 如果窗口大小超过了 k+1，则移动左指针缩小窗口
while (right - left + 1 > k + 1 && left <= right) {
sum -= A[left];
left++;
}
// 更新最大水量
if (right - left + 1 == k + 1) { // 只有当窗口大小正好为 k+1 时才更新最大值
max_sum = max(max_sum, sum);
}
// 移动右指针扩大窗口
right++;
}
// 输出最终能够喝到的最大水量
cout << max_sum << endl;
return 0;
}代码说明
- 输入部分：读入水壶的数量
n和最大操作次数k，以及每个水壶的初始水量。 - 初始化：
sum用于存储当前窗口内的元素总和，left和right分别作为窗口的左右边界。 - 循环体：
- 使用
right指针扩展窗口，直到遍历完整个数组。 - 每次扩展窗口时，如果窗口大小超过了
k+1，则通过移动left指针缩小窗口，直到窗口大小不超过k+1。 - 在每次窗口大小正好为
k+1时，更新最大水量max_sum。
- 使用
- 输出：输出找到的最大水量。
示例运行
假设输入如下：
10
5
890 965 256 419 296 987 45 676 976 742程序将执行以下步骤：
- 初始化
sum=0,left=1,right=1,max_sum=0。 - 开始滑动窗口：
right=1:sum=890right=2:sum=1855- ...
- 当
right=6时，sum=3813，此时窗口大小为k+1=6，更新max_sum=3813。 - 继续移动
right，直到遍历完整个数组。
- 最终输出结果为
3813。
这种方法的时间复杂度为 O(n)，因为我们只遍历了数组一次。空间复杂度为 O(1)，因为我们只使用了常数级别的额外空间。
代码4-滑动窗口/双指针
✅ 正确做法是什么？
这个问题是一个经典的 滑动窗口/双指针 类型的题目。
正确思路如下：
- 我们可以将最多连续 k+1 个元素合并成一个水壶（因为最多能通过 k 次操作把 k 个相邻水壶的内容合并到一个水壶里）。
- 所以我们要找出长度为 k+1 的连续子数组，使得它们的和最大。
举个例子：
如果 k = 3 ，那么最多可以把 3 次操作用来把 4 个相邻水壶的水全部倒进某一个里面。
所以我们只需要找所有长度为 k+1 的子数组的最大和即可。
✅ 时间复杂度：
- 使用滑动窗口法可以在 $O(n)$ 时间内完成。
✅ AC 版本代码如下：
#include <bits/stdc++.h>
using namespace std;
// 最大数组容量，防止越界
const int MAXN = 1e6 + 10;
int A[MAXN]; // 存储每个水壶初始水量，下标从1开始
int main() {
int n, k;
cin >> n >> k; // 输入水壶数量n和最多操作次数k
// 读取每个水壶的初始水量，注意我们从下标1开始存储
for (int i = 1; i <= n; ++i) {
cin >> A[i];
}
/*
* 示例输入：
* 10
* 5
* 890 965 256 419 296 987 45 676 976 742
*
* 我们要找的是：最多能通过 k 次操作把连续的 k+1 个水壶合并成一个的最大值。
* 因此我们需要找出长度为 k+1 的最大子数组和。
*/
long long sum = 0; // 当前窗口内的水量总和
// 初始时，计算第一个长度为 k+1 的窗口的水量总和
// 即前 k+1 个水壶的水量之和
// 注意边界条件：不能超过n
for (int i = 1; i <= k + 1 && i <= n; ++i) {
sum += A[i];
}
long long max_sum = sum; // 初始化最大水量为当前窗口的水量
// 使用滑动窗口向右移动
// 每次将窗口右边的一个元素加入窗口，并移除最左边的一个元素
for (int i = k + 2; i <= n; ++i) {
// 窗口滑动：加入右边新元素 A[i]，移除左边旧元素 A[i - k - 1]
sum += A[i] - A[i - k - 1];
// 更新最大水量
if (sum > max_sum) {
max_sum = sum;
}
}
// 输出最终能够喝到的最大水量
cout << max_sum << endl;
return 0;
}🔁 总结
你的做法 | 错误原因 |
|---|---|
贪心地每次合并相邻两数之和最大的位置 | 局部最优不等于全局最优，无法保证最终得到最大值 |
正确做法 | 原理 |
|---|---|
滑动窗口法，找出长度为 k+1 的最大子数组和 | 因为最多能通过 k 次操作把 k+1 个水壶合并成一个 |
现场真题注意事项
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;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
