蒟蒻求助大佬 STL 10分代码。。。

Scarlet_Lightning @ 2018-08-24 15:27:34

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue <int> q;
queue <int> qs;
int n,k,m;
int sum=0,sks;
void read(int &n)
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    n=x*f;
}
int main()
{
    read(n);
    read(k);
    read(m);
    cout<<"0"<<endl;
    cout<<m<<endl;
    q.push(m);
    sks=m;
    for(int i=2;i<=n-1;++i)
    {
        read(m);
        if(q.empty()){
            q.push(m);
            continue;
        }
        while(m<q.back()){ 
            if(q.front()<m){
                qs.push(q.front());
            }
            q.pop();
            if(q.empty())break;
            while(!qs.empty()){
                q.push(qs.front());
                qs.pop();
            }
        }
        q.push(m);
        while(q.size()>k){
            q.pop();
        }
        if(q.front()==sks){
            sum++;
            if(sum>=k){
            q.pop();
            sum=0;
            }
        }
        else{
            sum=0;
            sks=q.front();
        }
        cout<<q.front()<<endl;
    }
    cout<<endl;
    return 0;
}

by ACgod @ 2018-08-24 15:39:27

王瑞？

by 引领天下 @ 2018-08-24 15:43:42

@MKL_SCAR STL的deque不是这么用的啊……敢问您是怎么判断不在窗口的……

附上我丑陋的代码：

#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
struct Num{
    int index,x;//index为入队时间，x为数值
}a[MAXN];
int n,m,b[MAXN];
deque<Num> q,p;
int main(void){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].index=i;//读入
    for (int i=1;i<=n;i++){
        if (q.empty())q.push_back(a[i]);//如果没有直接入队
        while (!q.empty()&&q.front().index+m<=i)q.pop_front();//越界，从队头出队
        while (!q.empty()&&q.back().x>=a[i].x)q.pop_back();//前面的值大了，从队尾出队
        q.push_back(a[i]);//入队
        b[i]=q.front().x;//这里是更新后的队头
    }puts("0");
    for (int i=1;i<n;i++)printf ("%d\n",b[i]);
    return 0;
}

by Scarlet_Lightning @ 2018-08-24 15:45:53

@引领天下 emmm。。。我用的是queue。。。（我才不会告诉你我不会用deque呢！）

by 引领天下 @ 2018-08-24 15:52:11

@MKL_SCAR 那你很棒啊……我才不会告诉你我不会用queue模拟从队头出队

by std__Piggium @ 2018-08-24 15:52:36

你为何要用STL

by std__Piggium @ 2018-08-24 15:54:03

是不是闲着没事干

by Scarlet_Lightning @ 2018-08-24 16:15:37

@引领天下 不是的，我是又开了一个queue来存储那些被我本来不该弹掉的数据的。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue <int> q;//这个是模拟队列
queue <int> qs;//这个是上面说的临时容器
int n,k,m;
int sum=0,sks;//必须保证一个点不能在队列里待超过k的时间
void read(int &n)
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    n=x*f;
}
int main()
{
    read(n);
    read(k);
    read(m);
    cout<<"0"<<endl;
    cout<<m<<endl;
    q.push(m);
    sks=m;
    for(int i=2;i<=n-1;++i)
    {
        read(m);
        if(q.empty()){//如果队列为空那么无条件入队
            q.push(m);
            continue;
        }
        while(m<q.back()){ //从队尾开始比较
            if(q.front()<m){//如果队头元素<m，那么这个元素是不该弹掉的，压入临时容器
                qs.push(q.front());
            }
            q.pop();
            if(q.empty())break;//队列弹空了就不能再弹了，不然会RE。
            while(!qs.empty()){//把之前误弹的元素重新压回队列
                q.push(qs.front());
                qs.pop();
            }
        }
        q.push(m);//元素入队
        while(q.size()>k){//队列过大，把队头挤出去
            q.pop();
        }
        if(q.front()==sks){
            sum++;
            if(sum>=k){
            q.pop();
            sum=0;//如果队头元素在队列里呆了超过k的时间，那么请他滚蛋
            }
        }
        else{//更新当前正在计算的元素
            sum=0;
            sks=q.front();
        }
        cout<<q.front()<<endl;//输出队头最小值
    }
    cout<<endl;
    return 0;
}

by Scarlet_Lightning @ 2018-08-24 16:18:01

好吧，是我把一个语句写错位置了emmmmmm

by Scarlet_Lightning @ 2018-08-24 16:19:04

现在40分。。。