lz2018 @ 2018-11-03 16:57:46
刚接触单调队列,求帮助
才30分, 手打的几组样例过了
#include<iostream>
using namespace std;
long long l[10000001],l1[10000001],l2[10000001];
long long n,k,h,t;
void down(){
l1[1]=l[1];t=h=1;
for(int i=1;i<=n;i++){
if(l[i]<=l1[h]){
l1[i]=l[i];
t=h=i;
}
else {
int p=t;
while(l[i]<l1[p]&&p>=h){
l1[p]=99999999;
p--;
}
l1[++t]=l[i];
}
if(t-h==k)h++;
while(l1[h]==99999999&&h<=t)h++;
if(i>=k)cout<<l1[h]<<" ";
}
cout<<endl;
}
void up(){
l2[1]=l[1];t=h=1;
for(int i=1;i<=n;i++){
if(l[i]>=l1[h]){
l2[i]=l[i];
t=h=i;
}
else {
int p=t;
while(l[i]>l2[p]&&p>=h){
l2[p]=-99999999;
p--;
}
l2[++t]=l[i];
}
if(t-h==k)h++;
while(l2[h]==-99999999&&h<=t)h++;
if(i>=k)cout<<l2[h]<<" ";
}
cout<<endl;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>l[i];
down();
up();
return 0;
}
by lz2018 @ 2018-11-03 17:03:24
为什么没有回复-_-
by hpbl @ 2018-11-03 17:09:27
因为您的代码有点丑
by lz2018 @ 2018-11-03 17:11:32
@lhy930 我也这么觉得
by lz2018 @ 2018-11-03 17:14:39
问题已找到,本帖完结
by lz2018 @ 2018-11-03 17:20:44
忠告!!!
:
最大值一定要大的彻底
最小值一定要小的彻底
!!!!!!!!