poj 2823 二分法+单调队列

#include<stdio.h>

#include<string.h>

#define N 1100000

int a[N];

int fmin[N],fmax[N];

int tmin[N],tmax[N];

int dicmax(int l,int r,int f[],int k) {

int mid;

while(l<=r) {

mid=(l+r)/2;

if(k>=f[mid])//

r=mid-1;

else

l=mid+1;

}

return l;//这里的r返回第一个大于k的数的位置-1

}

int dicmin(int l,int r,int f[],int k) {

int mid;

while(l<=r) {

mid=(l+r)/2;

if(k<=f[mid])

r=mid-1;

else

l=mid+1;

}

return l;//

}

int main() {

int n,k,i,j,front,end;

while(scanf("%d%d",&n,&k)!=EOF) {

for(i=1;i<=n;i++)

scanf("%d",&a[i]);

front=end=1;

fmin[front]=a[1];

tmin[front]=1;

for(i=2;i<=k;i++) {

end=dicmin(front,end,fmin,a[i]);

// printf("%d\n",end);

fmin[end]=a[i];

tmin[end]=i;

}

printf("%d",fmin[front]);

for(i=k+1;i<=n;i++) {

end=dicmin(front,end,fmin,a[i]);

fmin[end]=a[i];

tmin[end]=i;

while(tmin[front]<i-k+1&&front<=end)

front++;

printf(" %d",fmin[front]);

}

printf("\n");

front=end=1;

fmax[1]=a[1];

tmax[1]=1;

for(i=2;i<=k;i++) {

end=dicmax(front,end,fmax,a[i]);

fmax[end]=a[i];

tmax[end]=i;

}

printf("%d",fmax[front]);

for(i=k+1;i<=n;i++) {

end=dicmax(front,end,fmax,a[i]);

fmax[end]=a[i];

tmax[end]=i;

while(tmax[front]<i-k+1&&front<=end)

front++;

printf(" %d",fmax[front]);

}

printf("\n");

}

return 0;}

巴特西

poj 2823 二分法+单调队列

最新文章

热门文章