UNIQUEx @ 2021-08-26 15:15:20
#include <stdio.h>
#include <stdlib.h>
int max(int);
int min(int);
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int a[10000100],b[10000100],c[10000100];
int top,topnum,k;
int main(int argc, char *argv[])
{
int n;//n表示一共有多少个数字,k代表一次性可以扫描多少个数
int i,j;
scanf("%d",&n);
scanf("%d",&k);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
topnum=min(1);
b[1]=topnum;
top=1;
int t=1;
int tnum=max(1);
c[1]=tnum;
for(i=2;i<=n-k+1;i++)
{
if(top<i)
{
topnum=min(i);
b[i]=topnum;
}
else
{
if(a[top]>a[i+k-1])
{
top=i+k-1;
topnum=a[i+k-1];
b[i]=a[i+k-1];
}
else
{
b[i]=topnum;
}
}
if(t<i)
{
tnum=max(i);
c[i]=tnum;
}
else
{
if(a[t]>a[i+k-1])
{
t=i+k-1;
tnum=a[i+k-1];
c[i]=a[i+k-1];
}
else
{
c[i]=tnum;
}
}
}
for(i=1;i<=n-k+1;i++)
{
printf("%d ",b[i]);
}
printf("\n");
for(i=1;i<=n-k+1;i++)
{
printf("%d ",c[i]);
}
return 0;
}
int max(int c)
{
int i,temp=-2147483647;
for(i=c;i<c+k;i++)
{
temp=temp>a[i]?temp:a[i];
}
return temp;
}
int min(int c)
{
int i,temp=2147483647;
for(i=c;i<c+k;i++)
{
temp=temp<a[i]?temp:a[i];
}
return temp;
}
by Moeebius @ 2021-08-26 15:22:39
这道题需要用单调队列……