poj2823,应用单调队列解题的思路
发布日期:2021-08-28 13:15:43 浏览次数:16 分类:技术文章

本文共 2198 字,大约阅读时间需要 7 分钟。

 关于单调队列的解释,这里有篇博文我认为讲得很好:

,可以参考。我自己简单的总结了一下单调队列这种数据结构的性质:

    1 、在队列里的元素一定是value单调递增(或者递减),而index单调递增。所以         队列中的头元素要么最大,要么最小。

       怎么保证这种性质呢,很简单,留在队列的元素在数组中并不是连续的。比如         array=1 4 7 3 2 ,在某个时刻,队列头元素为4,那么队列的结构有可能是4         3 2,而7就被跳过了。

    2、 单调队列只允许从末尾加入元素,而允许从两端删除元素。

   我这里就只贴代码,我这里用了两种方式来实现单调队列。针对poj2823那道题。

   第一种:运用STL的Deque(双端队列):

 

 
  1. #include<deque> #include<stdio.h> using namespace std; #define M 1000005 int a[M]; char ch[2*M]; int n,k; int index; int getInt(){ int u=1,data=0; while(ch[index]<='0'||ch[index]>='9')index++; if(index>0&&ch[index-1]=='-')u=-1; while(ch[index]>='0'&&ch[index]<='9'){ data=data*10+ch[index]-'0'; index++; } return data*u; } int main(){ scanf("%d %d",&n,&k); int i; getchar(); gets(ch); index=0; for(i=1;i<=n;i++){ a[i]=getInt(); } deque<pair<int,int> > D(M); for(i=1;i<k;i++){ while(!D.empty()&&a[i]<=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); } for(i=k;i<=n;i++){ while(!D.empty()&&a[i]<=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); while(D.front().second<=i-k)D.pop_front(); printf("%d ",D.front().first); } printf("\n");D.clear(); for(i=1;i<k;i++){ while(!D.empty()&&a[i]>=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); } for(i=k;i<=n;i++){ while(!D.empty()&&a[i]>=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); while(D.front().second<=i-k)D.pop_front(); printf("%d ",D.front().first); } return 0; }
  2.  

这一种在poj上提交超时。

第二种:自己用数组实现单调队列:

 

 
  1. #include<stdio.h> 
  2. #define M 2000005 
  3. int a[M],Q[M],I[M]; 
  4. int i,n,k; 
  5. void getMax(){ 
  6.     int head=1,tail=0; 
  7.     for(i=1;i<k;i++){ 
  8.         while(head<=tail&&Q[tail]<=a[i])tail--; 
  9.         tail++; 
  10.         Q[tail]=a[i];I[tail]=i; 
  11.     } 
  12.     for(i=k;i<=n;i++){ 
  13.         while(head<=tail&&Q[tail]<=a[i])tail--; 
  14.         tail++; 
  15.         Q[tail]=a[i];I[tail]=i; 
  16.         while(I[head]<=i-k)head++; 
  17.         printf("%d ",Q[head]); 
  18.     } 
  19. void getMin(){ 
  20.     int head=1,tail=0; 
  21.     for(i=1;i<k;i++){ 
  22.         while(head<=tail&&Q[tail]>=a[i])tail--; 
  23.         tail++; 
  24.         Q[tail]=a[i];I[tail]=i; 
  25.     } 
  26.     for(i=k;i<=n;i++){ 
  27.         while(head<=tail&&Q[tail]>=a[i])tail--; 
  28.         tail++; 
  29.         Q[tail]=a[i];I[tail]=i; 
  30.         while(I[head]<=i-k) head++; 
  31.         printf("%d ",Q[head]); 
  32.     } 
  33. int main(){ 
  34.     scanf("%d %d",&n,&k); 
  35.     for(i=1;i<=n;i++) 
  36.         scanf("%d",&a[i]); 
  37.     getMin(); 
  38.     printf("\n"); 
  39.     getMax(); 
  40.     return 0; 

这种就AC了。注明一下,第二种是我在网上找到的代码,不是自己写的!

转载地址:https://blog.csdn.net/weixin_33961829/article/details/85083102 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:VMware虚拟化技术培训(2)了解vSphere
下一篇:程序与生活:为什么要工作?

发表评论

最新留言

很好
[***.229.124.182]2024年02月29日 20时45分42秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章