信息学奥赛一本通 1333：【例2-2】Blah数集 | OpenJudge NOI 3.4 2729:Blah数集

【题目链接】

ybt 1333：【例2-2】Blah数集
OpenJudge NOI 3.4 2729:Blah数集

【题目考点】

1. 队列

【解题思路】

要填入Blah数集的一共有两类数
第一类：由2x+1生成的数
第二类：由3x+1生成的数
那么开两个队列q2与q3，分别存储由2x+1和3x+1生成的数字。这两个队列中的数字一定是单调递增的。
不断比较两个队列的队首元素，出队较小的值，这样得到的数字是单调不减的。两个队列队首的数字可能相同，而集合中相同的数字只有一个，这种情况下两个队列同时出队，但升序序列中只增加1个数字。升序序列中第n个数，就是Blah数集中的第n个数。
具体做法：
先通过输入的基a生成2a+1与3a+1，分别入队到q2与q3中。此时计数为1。
这两个队列队首比较，哪个数更小，哪个数就出队。若相等，则同时出队。
将刚刚出队的数字设为a，计数增加1，并将2*a+1，3*a+1分别入队。
计数增加到n时，此时a的值就是Blah数集中第n小的数字。

【题解代码】

写法1：用数组与表达式实现队列

#include <bits/stdc++.h>
using namespace std;
#define N 1000005 
int q2[N], q3[N], a, n, h_2, t_2, h_3, t_3;//q2,q3:两个队列 h,t两个队列的头尾指针
int main()
{
    while(scanf("%d %d", &a, &n) != EOF)
    {
        h_2 = t_2 = h_3 = t_3 = 0;//清空两个队列
        int count = 1;//count计数
        q2[++t_2] = 2*a + 1;//入队
        q3[++t_3] = 3*a + 1;
        while(count < n)
        {
            if(q2[h_2+1] < q3[h_3+1])//队首比较
                a = q2[++h_2];//队列2出队
            else if(q2[h_2+1] > q3[h_3+1])
                a = q3[++h_3];//队列3出队
            else//二者相等，都出队
            {
                a = q2[++h_2];
                ++h_3;
            }
            q2[++t_2] = 2*a + 1;//入队
            q3[++t_3] = 3*a + 1;
            count++;
        }
        printf("%d\n", a);
    }
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

写法2：使用C++ STL

#include<bits/stdc++.h>
using namespace std;
int main()
{   
	queue<int> q2, q3;
	int a, n;
	while(cin >> a >> n)
	{
		q2 = queue<int>();//清空队列 
		q3 = queue<int>();
		for(int i = 2; i <= n; ++i)//求第i小的值，初始情况a是第1小的值 
		{
			q2.push(2*a+1);
			q3.push(3*a+1);
			if(q2.front() > q3.front())//如果3x+1队列队首更小 
			{
				a = q3.front();
				q3.pop();
			}
			else if(q2.front() < q3.front())//如果2x+1队列队首更小
			{
				a = q2.front();
				q2.pop();
			}
			else
			{
				a = q2.front();
				q2.pop();
				q3.pop();
			}
		}
		cout << a << endl;
	} 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35