FincheuwYggdrasil @ 2022-11-07 22:01:26
RT
#include<bits/stdc++.h>
using namespace std;
deque<int> a;
int n,k,l;
int a0[100010],min0[100010],max0[100010];
int main()
{
scanf("%d%d",&n,&k);
fill(max0,max0+n+1,INT_MIN);
fill(min0,min0+n+1,INT_MAX);
for(int i = 1;i <= n;i++)
scanf("%d",&a0[i]);
for(int i = 1;i <= k;i++)
{
a.push_back(a0[i]);
min0[1] = min(min0[1],a0[i]);
max0[1] = max(max0[1],a0[i]);
}
l = n - k + 1;
for(int i = 2;i <= l;i++)
{
int now = a0[k + i - 1];
a.pop_front();
a.push_back(now);
int minn = INT_MAX,maxx = INT_MIN;
for(int i = 0;i < a.size();i++)
{
minn = min(a.front(),minn);
maxx = max(a.front(),maxx);
a.push_back(a.front());
a.pop_front();
}
max0[i] = maxx;
min0[i] = minn;
}
for(int i = 1;i <= l;i++)
{
printf("%d ",min0[i]);
}
printf("\n");
for(int i = 1;i <= l;i++)
{
printf("%d ",max0[i]);
}
return 0;
}
by 无敌的神 @ 2022-11-26 11:09:32
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int MAX=1e6+1;
int n,k;
int q[MAX],a[MAX];//用数组模拟
void calmin(){//最小值
int h=0,t=1;//初始化队列
for(int i=1;i<=n;i++){
while(h<=t&&a[i]<=a[q[t]]) t--;//防止越界和单调递增
q[++t]=i;//入队
while(h<=t&&q[h]<=i-k) h++;//滑动窗口（抛掉无用数据）
if(i>=k) printf("%d ",a[q[h]]);//队首是最优值（此处是最大值）
}
}
void calmax(){//最大值
int h=0,t=1;
for(int i=1;i<=n;i++){
while(h<=t&&a[i]>=a[q[t]]) t--;//防止越界和单调递减
q[++t]=i;
while(h<=t&&q[h]<=i-k) h++;
if(i>=k) printf("%d ",a[q[h]]);
}
}//其他和"calmin"一样
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入
calmin();
printf("\n");
calmax();//调用函数和换行
}