Blue_Flower @ 2023-09-11 22:15:24
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,h1=1,r1=1,h2=1,r2=1;
struct node{
int id;
ll data;
}w1[10000100],w2[10000100]; //懒得写循环队列，防越界多开了10倍的数组（虽然用不了那么大）
//w1:升序 w2:降序
ll read() //快读
{
char x=getchar();
ll res=0,f=1;
if(x=='-') f=-1;
while(x<'0'||x>'9') x=getchar();
while(x>='0'&&x<='9')
{
res=res*10+x-'0';
x=getchar();
}
return res*f;
}
vector<ll> ans1,ans2; //不知为何就是想用vector存答案
int main()
{
n=read();k=read();
int tmp;
w1[0].data=100000000000;
for(int i=1;i<=n;i++)
{
tmp=read();
//升序队列
while(i-k>=w1[h1].id) h1++;
while(tmp<w1[r1-1].data&&r1>h1) r1--;
w1[r1].data=tmp;w1[r1++].id=i;
//降序队列
while(i-k>=w2[h2].id) h2++;
while(tmp>w2[r2-1].data&&r2>h2) r2--;
w2[r2].data=tmp;w2[r2++].id=i;
//存答案
if(i>=k)
{
ans1.push_back(w1[h1].data);
ans2.push_back(w2[h2].data);
}
}
int len=ans1.size();
for(int i=0;i<len;i++) printf("%lld ",ans1[i]);
puts("");
for(int i=0;i<len;i++) printf("%lld ",ans2[i]);
}输入： 10 3 -94 21 24 73 38 77 11 73 9 -88 输出： -94 21 24 38 11 11 9 -88 24 73 73 77 77 77 73 73
by liuxy1234 @ 2023-09-11 22:19:10
访问w2的时候w2[h2]可能越界（w2为空，h2=1）
by Blue_Flower @ 2023-09-11 22:22:02
@liuxy1234 感谢dalao
by Blue_Flower @ 2023-09-11 22:28:32
@liuxy1234 不好意思能讲详细些吗，由于我太蒻了，想到的改进是这样的
int tmp;
w1[1].data=w2[1].data=read();
w1[1].id=w2[1].id=1;
for(int i=2;i<=n;i++)然后就多WA了一个点
by liuxy1234 @ 2023-09-11 22:46:10
@liuhanming__nb 这两个下标从0开始设
by Blue_Flower @ 2023-09-11 22:49:30
@liuxy1234 就是队列头指针吗
by liuxy1234 @ 2023-09-11 23:07:22
@liuhanming__nb 实在是调不动了，一直90pts WA#1，我直接把我代码放这吧
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1001000], q[1001000], M, n;
signed main()
{
cin >> n >> M;
for(int i = 1;i <= n;i++)scanf("%lld", &a[i]);
q[1] = 1;
int front = 1, rear = 1;
for(int i = 1;i <= n;i++)
{
//入队尾
while(front <= rear && a[q[rear]] >= a[i])rear--;
q[++rear] = i;
//删队首
while(front <= rear && q[front] <= i - M)front++;
//取队首
if(i > M - 1)cout << a[q[front]] << " ";
}
puts("");
q[1] = 1;
front = 1, rear = 1;
for(int i = 1;i <= n;i++)
{
//入队尾
while(front <= rear && a[q[rear]] <= a[i])rear--;
q[++rear] = i;
//删队首
while(front <= rear && q[front] <= i - M)front++;
//取队首
if(i > M - 1)cout << a[q[front]] << " ";
}
return 0;
}by liuxy1234 @ 2023-09-11 23:11:28
@liuhanming__nb wc调出来了，是你的read出问题了……
by liuxy1234 @ 2023-09-11 23:12:34
@liuxy1234 就是判断正负不一定进来第一个就是 -，建议把判断负号放进while不是数字里，像这样
inline int read()
{
register int x = 0, f = 1;
register char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')f = -1;
c = getchar();
}
while(c <= '9' && c >= '0')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}by Blue_Flower @ 2023-09-12 21:23:50
@liuxy1234 昨天睡着了感谢dalao
by Blue_Flower @ 2023-09-12 21:34:15
@liuxy1234 我自己再调了一下过了，其实把判断队首元素过期的语句放在入队语句后就行了，快读的问题感谢，之前我一直写的都是错的
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,h1=0,r1=0,h2=0,r2=0;
struct node{
int id;
ll data;
}w1[10000100],w2[10000100];
inline ll read()
{
int x = 0, f = 1;
char c = getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
vector<ll> ans1,ans2;
int main()
{
n=read();k=read();
int tmp;
w1[0].data=10000000000;
for(int i=1;i<=n;i++)
{
tmp=read();
while(tmp<w1[r1-1].data&&r1>h1) r1--;
w1[r1].data=tmp;w1[r1++].id=i;
while(i-k>=w1[h1].id) h1++;
while(tmp>w2[r2-1].data&&r2>h2) r2--;
w2[r2].data=tmp;w2[r2++].id=i;
while(i-k>=w2[h2].id) h2++;
if(i>=k)
{
ans1.push_back(w1[h1].data);
ans2.push_back(w2[h2].data);
}
}
int len=ans1.size();
for(int i=0;i<len;i++) printf("%lld ",ans1[i]);
puts("");
for(int i=0;i<len;i++) printf("%lld ",ans2[i]);
}