【luogu P2947 [USACO09MAR]向右看齐Look Up】 题解
2024-08-30 08:51:56
题目链接:https://www.luogu.org/problemnew/show/P2947
因为在单调队列上被dalao们锤爆
怒刷单调队列题
何为单调队列?
设我们的队列为从左至右单调递增
对于样例数据 3 2 6 1 1 2
我们先把3入队 此时队列:3
再将2从后面入队 此时队列:2 3
再将6从后面入队 但是,为了满足队列从左至右的单调性,我们将2,3出队 此时队列:6
再将1从后面入队 此时队列:1 6
再将1从后面入队 此时队列:1 1 6
再将2从后面入队 但是,为了满足队列从左至右的单调性,我们将1,1出队 此时队列:2 6
由此可以类推其他单调性。
于是,我们观察到单调队列和这道题的关系:
“谁把我从队列里赶了出去我就仰望谁。”
所以,2,3被6赶出去,2,3仰望的位置为6的位置即3。
所以,1,1被2赶出去,1,1仰望的位置为2的位置即6。
那么,如果我一直在队里。我就谁也不仰望。
下面介绍实现方式:
我先说:
"我永远都喜欢\(Stella\)!"
没良心的Master
单调队列需要一个支持从两边操作的队列——双端队列
\(STL\)中有现成的deque:
\(code:\)
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
struct node{
int pos, val;
}a[maxn];//因为我们需要记录位置,所以开一个结构体。val为高度,pos为在序列的位置。
int n, ans[maxn];
deque<node> q;//双端队列。
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i].val); a[i].pos = i;//输入高度,给位置赋值。
while(!q.empty() && a[i].val > q.back().val) ans[q.back().pos] = a[i].pos, q.pop_back();//当队列不为空时,如果当前输入的值大于我队列中后面的元素值,那么我就要仰望当前的输入值的位置。同时把我出队。
q.push_back(a[i]);//从后面将元素入队。
}
for(int i = 1; i <= n; i++)
printf("%d\n",ans[i]);
return 0;
}
至于为什么需要一个支持两头操作的队列。
在大部分单调队列题目中,需要维护的区间有时并不是整一个区间,而是多个区间。所以当如果我们单调队列中最前面的数已经不在当前区间里,我们需要将他从前面出队。
最前面的数一定比当前维护好的队列里所有数入队都早。如果他入队不是最早还比之前入队的数大,前面入队的数直接被他挤出队了。
欢迎交流/指错
一起共同进步。
QQ:935145183/3203600070
最新文章
- 《小白的CFD之旅》招募写手
- hadoop学习笔记:zookeeper学习(上)
- 【代码笔记】iOS-标题2个图标,点击的时候,页面跳转
- jQuery数组($.each,$.grep,$.map,$.merge,$.inArray,$.unique,$.makeArray)处理函数详解
- 深入理解js——执行上下文
- {dockerUI}在服务器上直接安装shipyard/shipyard
- HDU4901 The Romantic Hero 计数DP
- CSS控制";标题前增加小图标或编号";
- DBA常用SQL之会话与等待事件
- SPRING IN ACTION 第4版笔记-第十一章Persisting data with object-relational mapping-004JPA例子的代码
- Python Tutorial 学习(九)--Classes
- linux中VI编辑器使用个人记录
- XAML 名称范围
- SharePoint使用BCS开发你第一个应用程序(三)
- (转)多个MapReduce作业相互依赖时,使用JobControl进行管理
- 由内搜推送思考Kafka 的原理
- 剑指Offer-不用加减乘除做加法
- Luogu1613 跑路
- nginx 10054报错问题解决方案
- hi-nginx-1.4.9正式发布,支持javascript后端开发