dw 网页设计与制作教程,wordpress优化插件,郑州做网站优化的公,购物网站管理系统P1901 发射站 245通过468提交题目提供者该用户不存在标签NOI导刊云端↑难度普及/提高-时空限制1s / 128MB提交 讨论 题解 最新讨论更多讨论 大神路过的看一下输入后面为什么带空格。有人说是单调队列#xff0c;但不明明…题目描述 某地有 N 个能量发射站排成一行#xf… P1901 发射站 245通过468提交题目提供者该用户不存在标签NOI导刊云端↑难度普及/提高-时空限制1s / 128MB 提交 讨论 题解 最新讨论更多讨论 大神路过的看一下输入后面为什么带空格。有人说是单调队列但不明明… 题目描述 某地有 N 个能量发射站排成一行每个发射站 i 都有不相同的高度 Hi并能向两边当 然两端的只能向一边同时发射能量值为 Vi 的能量并且发出的能量只被两边最近的且比 它高的发射站接收。 显然每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受特别是为了安 全每个发射站接收到的能量总和是我们很关心的问题。由于数据很多现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。 输入输出格式 输入格式 第 1 行一个整数 N; 第 2 到 N1 行第 i1 行有两个整数 Hi 和 Vi表示第 i 个人发射站的高度和发射的能量值。 输出格式 输出仅一行表示接收最多能量的发射站接收到的能量值答案不超过 longint。 输入输出样例 输入样例#13
4 2
3 5
6 10输出样例#17 说明 对于 40%的数据1N50001Hi1000001Vi10000; 对于 70%的数据1N1000001Hi2,000,000,0001Vi10000; 对于 100%的数据1N1000000;1Hi2,000,000,0001Vi10000。 分析直接暴力肯定是不行的如果我们从某一点i考虑,那么其左边比它小的则可以忽略右边也同样如此也就是说我们需要设计一种数据结构使得可以快速查找到i左右比它大的第一个点可以利用单调栈。和单调队列不同单调栈只能在栈顶进行操作但维护方法差不多如果要维护递增的则从栈顶弹出元素直到比当前值大这里说的递增是从栈顶到栈尾。对于本题而言我们只需要维护两次单调栈即可. #include iostream
#include cstdlib
#include cstdio
#include cstring
#include string
#include algorithm
#include queue
#include stackusing namespace std;int n, h[1000010], v[1000010],top,stk[1000010],num[1000010],t[1000010],ans;void update(int x)
{while (top t[top] h[x])top--;num[stk[top]] v[x];stk[top] x;t[top] h[x];
}int main()
{scanf(%d, n);for (int i 1; i n; i)scanf(%d%d, h[i], v[i]);for (int i 1; i n; i)update(i);top 0;for (int i n; i 1; i--)update(i);for (int i 1; i n; i)ans max(ans, num[i]);printf(%d\n, ans);return 0;
} 转载于:https://www.cnblogs.com/zbtrs/p/7041717.html
