信奥赛-刷题笔记-栈篇-T3-P1901发射站0521

总题单

本部分总题单如下

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

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

栈篇题单

P1901 发射站

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

题目描述

某地有 $N$ 个能量发射站排成一行，每个发射站 $i$ 都有不相同的高度 $H_i$，并能向两边（两端的发射站只能向一边）同时发射能量值为 $V_i$ 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 $0$ 或 $1$ 或 $2$ 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

输入格式

第 $1$ 行一个整数 $N$。

第 $2$ 到 $N+1$ 行，第 $i+1$ 行有两个整数 $H_i$ 和 $V_i$，表示第 $i$ 个发射站的高度和发射的能量值。

输出格式

输出仅一行，表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。

输入输出样例 #1

输入 #1

3
4 2 
3 5 
6 10

输出 #1

7

说明/提示

对于 $40\%$ 的数据，$1\le N\le 5000,1\le H_i\le 10^5,1\le V_i\le 10^4$。

对于 $70\%$ 的数据，$1\le N\le 10^5,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。

对于 $100\%$ 的数据，$1\le N\le 10^6,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。

代码1-暴力

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n;
int h[maxn],v[maxn],s[maxn];
int main(){
//	cout<<maxn<<endl;// 输入n 表示n个发射塔 cin>>n;// 输入n行 每行h高度 和 v能量for(int i=1;i<=n;i++){cin>>h[i]>>v[i];} // 每次都寻找左右两遍第1个比当前塔高度的大的，加上能量 for(int i=1;i<=n;i++){// 循环内要完成的事情 是 朝着两遍发射 然后接受if(i==1){// 只朝右发射 for(int j=i+1;j<=n;j++){if(h[j]>h[i]) {s[j]+=v[i]; break;}}}else if(i==n){// 只朝左发射 for(int j=i-1;j>=1;j--){if(h[j]>h[i]) {s[j]+=v[i]; break;}}			}else{// 朝右发射for(int j=i+1;j<=n;j++){if(h[j]>h[i]) {s[j]+=v[i]; break;}}// 朝左发射for(int j=i-1;j>=1;j--){if(h[j]>h[i]) {s[j]+=v[i]; break;}}}}//	for(int i=1;i<=n;i++){
//		cout<<h[i]<<v[i]<<" ";
//	} 	int t=s[1];for(int i=1;i<=n;i++){if(t<s[i]) t=s[i];	} cout<<t;return 0;
}/*3
4 2 
3 5 
6 107
*/

代码2

现在使用单调栈的技巧来解决这个问题，目的是高效地找到每个发射站左右两边第一个比它高的发射站。

#include<iostream>
using namespace std;const int maxn = 1e6 + 10; // 定义最大数组大小，支持最多1e6个发射站// sum[i] 表示第i个发射站接收到的能量总和
int s1[maxn], h[maxn], v[maxn], sum[maxn], ans, n, top;int main() {cin >> n;// 输入每个发射站的高度h[i]和能量值v[i]for(int i = 1; i <= n; i++) {cin >> h[i] >> v[i];// 单调栈处理：从栈顶弹出所有比当前发射站矮的发射站// 这些被弹出的发射站会把它们的能量v[s1[top]]传给当前发射站iwhile(top && h[s1[top]] < h[i]) {sum[i] += v[s1[top]]; // 当前发射站i接收来自这些发射站的能量top--; // 弹出栈顶}// 如果栈中还有元素（即存在未被处理的发射站）// 那么当前发射站i的能量v[i]会被传递给它左边第一个更高的发射站if (top > 0) {sum[s1[top]] += v[i]; // 栈顶发射站接收当前发射站i发出的能量}s1[++top] = i; // 将当前发射站i压入栈中}// 遍历所有发射站，找出接收能量最多的那个for(int i = 1; i <= n; i++) {ans = max(ans, sum[i]);}// 输出最终结果cout << ans << endl;return 0;
}
/*3
4 2 
3 5 
6 107
*/

下面是对这段代码的工作原理和逻辑的解释：

代码解析

1. 初始化变量：

   • maxn：定义了一个常量表示数组的最大大小。
   • s1[maxn]：这是一个栈，用来存储发射站的索引，用于寻找最近的比当前发射站高的发射站。
   • h[maxn], v[maxn]：分别存储每个发射站的高度和能量值。
   • sum[maxn]：存储每个发射站接收到的能量总和。
   • ans：记录接收最多能量的发射站所接收的能量值。
   • n：发射站的数量。
   • top：栈顶指针，初始化为0。

2. 输入数据：

   • 首先读取发射站的数量 n。
   • 然后循环读取每个发射站的高度 h[i] 和能量值 v[i]。

3. 处理每个发射站：

   • 对于每个发射站 i，使用一个 while 循环检查栈顶元素（即之前遇到的发射站），如果栈顶发射站的高度小于当前发射站的高度，则从栈中弹出，并将该发射站的能量值累加到当前发射站的接收能量中。
   • 将当前发射站的能量值累加给栈顶的发射站（如果有）。
   • 将当前发射站的索引压入栈中，准备处理下一个发射站。

4. 计算最大接收能量：

   • 最后遍历 sum 数组，找出接收能量最大的值，并将其赋值给 ans。

5. 输出结果：

   • 输出接收到最多能量的发射站的能量值。

关键点理解

• 单调栈的应用：通过维护一个高度递减的栈（s1），可以在O(n)的时间复杂度内找到每个发射站左右两边第一个比它高的发射站。这是因为每次新发射站加入时，都会“清理”掉那些比它矮的旧发射站，确保栈中的发射站高度总是递减的。

• 能量传递逻辑：当发现一个比当前发射站高的发射站时，当前发射站的能量就会被传递给那个更高的发射站。同时，当前发射站也会从栈中比它矮的发射站那里接收能量。

改进建议

虽然你的实现基本正确，但有一个小问题需要注意：在更新 sum[s1[top]]+=v[i]; 这行代码时，可能会尝试访问无效的栈顶元素（比如当栈为空时）。为了避免潜在的错误，可以考虑在这个操作之前添加一个条件判断 if(top > 0) 来确保栈不为空。此外，为了使代码更加清晰，可以考虑增加一些注释来解释每一步的目的。

现场真题注意事项

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;
}