Tim0509 @ 2023-03-30 18:36:33
以下代码使用结构体完成了单调队列
但是,在
而在
求奆佬指点
#include<bits/stdc++.h>
#define MP make_pair
#define PII pair<int,int>
using namespace std;
typedef long long ll;
const int INF=2e+9;
const int N=1e6+5;
int n,k;
int a[N];
struct que{
PII q[N];
int tail=-1,head=0,size=0;
int op=0;//维护区间最大
bool check(int x,int y){
if(op==1){
return x>y;
}else{
return x<y;
}
}
void clear(int opt){
op=opt;
tail=head-1;
}
PII front(){
return q[head];
}
PII back(){
return q[tail];
}
void pop_front(){
if(head>tail)return;
head++;
}
void pop_back(){
if(head>tail)return;
tail--;
}
void push(int id,int x){
PII New=MP(id,x);
while(head<=tail&&check(x,back().second))pop_back();
q[++tail]=New;
}
}q1,q2;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
q1.clear(0);
for(int i=1;i<=n;i++){
if(q1.front().first<i-k+1)q1.pop_front();
q1.push(i,a[i]);
if(i>=k)printf("%d ",q1.front().second);
}
puts("");
q2.clear(1);
for(int i=1;i<=n;i++){
if(q2.front().first<i-k+1)q2.pop_front();
q2.push(i,a[i]);
if(i>=k)printf("%d ",q2.front().second);
}
return 0;
}
by Tim0509 @ 2023-03-30 18:39:37
CE记录
AC记录
by bamboo12345 @ 2023-03-30 19:08:10
@Tim0509 好像是不能在结构体里直接赋值
by Tim0509 @ 2023-03-31 07:39:02
@bamboo123
已过,orz
int tail,head;
int op;//维护区间最大
bool check(int x,int y){
if(op==1){
return x>y;
}else{
return x<y;
}
}
void clear(int opt){
op=opt;
head=0;
tail=head-1;
}
↑修改后代码