【3月30日每日一题】 滑动窗口 Editional

滑动窗口

https://ac.nowcoder.com/acm/problem/50528

STL

单调队列具体来说,就是保证成员满足单调递增递减的队列。在新成员进入时,需要将他的权与队尾成员的权相比较,若将这个成员直接插入时不满足条件了,则将队尾出队,反复循环直至满足要求或队列为空为止。这时再插入便可以保证队列的单调性了。题目要求同时寻找最大值和最小值,则只需开两个单调队列即可。我们要的答案便是每次操作后队首元素的集合。

但要注意窗口可滑动。当窗口左端坐标超过队首时,这个队首不在窗口中。解决方法是在入队时记录该元素的坐标。在每次入队操作后开始从对首连续删除坐标不满足要求的元素,此时的对首才是我们要求的答案。

再注意要用的容器类型。因为要同时对队首和队尾进行操作,本题选择deque。

Code:

#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
using namespace std;
struct node
{
    int nu,ind;//分别是权值和坐标
}s;
deque<node>G;//记录最大值用的队列
deque<node>F;//记录最小值用的队列
int n,k,ma[2000000],mi[2000000];
void input(int w,int in)
{
    s.nu=w;
    s.ind=in;
    while(!G.empty() && s.nu>G.back().nu)G.pop_back();//删除不满足要求的队尾
    G.push_back(s);//压入    下面的操作同理
}
void init(int w,int in)
{
    s.nu=w;
    s.ind=in;
    while(!F.empty() && s.nu<F.back().nu)F.pop_back();//同上
    F.push_back(s);
}
void output(int in)
{
    while(G.front().ind<in)G.pop_front();//将窗体以左的队首出队
    while(F.front().ind<in)F.pop_front();//同上
}
int main()
{
    cin>>n>>k;
    int i,w;
    For(i,1,k)//先进入第一个窗体
    {
        cin>>w;
        input(w,i);
        init(w,i);
    }
    ma[1]=G.front().nu;
    mi[1]=F.front().nu;
    For(i,k+1,n)//滑动处理
    {
        cin>>w;
        input(w,i);
        init(w,i);
        output(i-k+1);
        ma[i-k+1]=G.front().nu;
        mi[i-k+1]=F.front().nu;
    }
    For(i,1,n-k+1)printf("%d ",mi[i]);putchar('\n');//输出
    For(i,1,n-k+1)printf("%d ",ma[i]);putchar('\n');
    return 0;
}
全部评论

相关推荐

来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 13:36
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务