当前位置: 代码迷 >> 综合 >> 队列做题:1333:Blah数集(单调队列)
  详细解决方案

队列做题:1333:Blah数集(单调队列)

热度:81   发布时间:2024-02-07 14:08:41.0

1333:Blah数集(单调队列)

又是一种奇怪的数据结构(算法),见得太少了。

注意:不是优先队列(堆)哟!!!。

讲解:

https://blog.csdn.net/sinat_40471574/article/details/90577147

代码一:

CV的。这个代码更好理解。

https://www.cnblogs.com/zwfymqz/p/6636579.html

#include<iostream>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
int tot=1;
int x;
int main()
{int x,n;while(cin>>x&&cin>>n){tot=1;queue<int>a;queue<int>b;while(tot<n){a.push(2*x+1);b.push(3*x+1);if(a.front()>b.front()){x=b.front();b.pop();}else if(a.front()<b.front()){x=a.front();a.pop();}else{x=a.front();a.pop();b.pop();}tot++;}cout<<x<<endl;}return 0;
}

代码二:

CV的

只比较第一个元素*3+1和第二个元素*2+1哪个小即可,把小的入队,并且队首指针+1,当两个数相同时,只入队其中一个,head1和head2同时+1,以此类推,维护单调递增序列,当tail==n时,输出队尾元素即可。

https://blog.csdn.net/cax1165/article/details/52937683

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1000010;
int a,n,head1,head2,tail,q[maxn];
int main()
{while(scanf("%d%d",&a,&n)>0){head1=head2=1;tail=1;q[head1]=a;while(tail<n){int x=q[head1]*2+1,y=q[head2]*3+1;if(x<y){q[++tail]=x;head1++;}else{if(y<x){q[++tail]=y;head2++;}else{q[++tail]=x;head1++;head2++;}}}printf("%d\n",q[tail]);}return 0;
}

用单调队列的原因是:一个个算的话前面的不一定比后面的小,如果用sort的话,前面的有可能已经出队了这样就无法保证队列从小到大。