【COGS495】窗口

时间：2021-07-31 09:17:57

【问题描述】

给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：

Window position Min value Max value
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5]3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7 ] 3 7

你的任务是找出窗口在各位置时的max value,min value．

【输入格式】

第一行n，k，第二行为长度为n的数组

【输出格式】

第一行每个位置的min value,第二行每个位置的max value

【分析】

好吧，其实我不想发上来的，纯粹凑数。

裸的单调队列。

 #include <cstdlib>

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <cstring>

 const int maxn=;

 const int INF=0x7fffffff;

 using namespace std;

 struct que{int shu[maxn],l,r;}Q_max,Q_min;

 void solve();

 void print();

 int data[maxn],n,k;

 int ans[][maxn];

 int main()

 {

     //文件操作

     freopen("window.in","r",stdin);

     freopen("window.out","w",stdout);

     scanf("%d%d",&n,&k);

     for (int i=;i<=n;i++) scanf("%d",&data[i]);

     solve();//滑动窗口

     print();//打印

     return ;

 }

 void solve()

 {

      //拉上窗口

      int i;

      Q_max.l=Q_min.l=Q_max.r=Q_min.r=;//初始化指针

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

      {

          while (Q_max.l<Q_max.r && Q_max.shu[Q_max.l]<i-k+) Q_max.l++;

          while (Q_min.l<Q_min.r && Q_min.shu[Q_min.l]<i-k+) Q_min.l++;

          while (Q_max.l<Q_max.r && data[Q_max.shu[Q_max.r-]]<data[i]) Q_max.r--;

          while (Q_min.l<Q_min.r && data[Q_min.shu[Q_min.r-]]>data[i]) Q_min.r--;

          Q_max.shu[Q_max.r++]=i;Q_min.shu[Q_min.r++]=i;

      }

      //注意窗口永远指向窗口最右端

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

      {

          while (Q_max.l<Q_max.r && Q_max.shu[Q_max.l]<i-k+) Q_max.l++;

          while (Q_min.l<Q_min.r && Q_min.shu[Q_min.l]<i-k+) Q_min.l++;

          ans[][i]=Q_max.shu[Q_max.l];ans[][i]=Q_min.shu[Q_min.l];//标记打印

          while (Q_max.l<Q_max.r && data[Q_max.shu[Q_max.r-]]<data[i+]) Q_max.r--;

          while (Q_min.l<Q_min.r && data[Q_min.shu[Q_min.r-]]>data[i+]) Q_min.r--;

          Q_max.shu[Q_max.r++]=i+;Q_min.shu[Q_min.r++]=i+;

      }

 }

 void print()

 {

      for (int i=k;i<=n;i++) printf("%d ",data[ans[][i]]);

      printf("\n");

      for (int i=k;i<=n;i++) printf("%d ",data[ans[][i]]);

 }

相关文章