NaN_HQJ2007_NaN @ 2019-11-10 20:47:27
#include<bits/stdc++.h>
using namespace std;
struct note{
int s,id;
};
const int maxn=1000000+5;
int n,k,i,j,ys,mi[maxn],ma[maxn];
note qmin[maxn];
note qmax[maxn];
int main(){
cin>>n>>k;
int head=1,tail=0,head2=1,tail2=0,z=0,z2=0;
for(i=1;i<=n;i++){
scanf("%d",&ys);
if(i-qmin[head].id>=k){
head++;
}
while(qmin[tail].s>=ys && tail-head>=0){
tail--;
}
qmin[++tail].s=ys;
qmin[tail].id=i;
if(i>=k){
mi[++z]=qmin[head].s;
}
//////////
/////////
if(i-qmax[head2].id>=k){
head2++;
}
while(qmax[tail2].s<=ys && tail2-head2>=0){
tail2--;
}
qmax[++tail2].s=ys;
qmax[tail2].id=i;
if(i>=k){
ma[++z2]=qmax[head2].s;
}
}
for(i=1;i<=z;i++){
cout<<mi[i]<<" ";
}
cout<<endl;
for(i=1;i<=z2;i++){
cout<<ma[i]<<" ";
}
return 0;
}
by NaN_HQJ2007_NaN @ 2019-11-10 20:47:49
各位请积极回答
by NaN_HQJ2007_NaN @ 2019-11-10 21:02:05
给为dalao不用了
by nonanalyzer @ 2019-11-10 21:22:54
@jasonhqj
if(i-qmin[head].id>=k){ head++; }
第三个点k=1,i=1时你这里head会变成2,而tail还是1,于是qmin[1]被正确赋值但qmin[head]取不到这个值
by nonanalyzer @ 2019-11-10 21:23:36
后面head总是比tail大1,所以你输出全是0
qmax同理
by NaN_HQJ2007_NaN @ 2019-11-10 21:30:09
谢谢!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!