洛谷 1886修正题解

· · 题解

因为先交了一份题解被洛谷说是重复题解特意重新写了一份；；；

这一次用的是deque

代码如下：

deque-->双向队列操作（由于搞忘了如何清空所以用了两个deque ￣□￣｜｜抱歉）

#include<bits/stdc++.h>
using namespace std;
int x;
struct sd
{
    int num,val; //存储编号和大小
};
deque<sd> que;
deque<sd> que1;
int add[3][1000005]; //用以存储答案的----见代码
int main()
{
    int n,m,k,cnt=1;
    cin>>n>>k;
    sd rr;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);  //输入
        rr.num=i; rr.val=x;  //赋值
        while(!que.empty()&&x>=que.back().val)
        que.pop_back();  //单调队列的操作，以保证单调
        while(!que1.empty()&&x<=que1.back().val)
        que1.pop_back();
        que.push_back(rr); //压入队列
        que1.push_back(rr);//同上
        while(i-k>=que.front().num)  //T掉不在范围内的
        que.pop_front();
        while(i-k>=que1.front().num)
        que1.pop_front(); //同上
        if(i>=k) 
        {
            add[0][cnt]=que.front().val;
            add[1][cnt]=que1.front().val;
            cnt++;
        } //存答案
    }
    for(int i=1;i<cnt;i++)
    printf("%d ",add[1][i]);
    printf("\n");
    for(int i=1;i<cnt;i++)
    printf("%d ",add[0][i]);  //输出
    return 0;
}

小结： deque其实很好用

对于普通数据结构费时挺多

deque没开O2 最长测试点400+ms

开了O2 最长测试点300+ms

给大家附上 deque用法

1 d[i]:返回d中下标为I的元素的引用。

2 d.front():返回的一个元素的引用。
3 d.back():返回最后一个元素的引用。
4 d.pop_back():删除尾部的元素。不返回值。
5 d.pop_front()：删除头部元素。不返回值。
6 d.push_back(e):在队尾添加一个元素e。
7 d.push_front(e):在对头添加一个元素e。