Informatics Olympiad 1333: [example 2-2] blah data set | openjudge noi 3.4 2729:blah data set

【 Topic link 】

ybt 1333：【 example 2-2】Blah Number set
OpenJudge NOI 3.4 2729:Blah Number set

【 Topic test site 】

1. queue

【 Their thinking 】

To fill in Blah There are two kinds of numbers in a number set
The first category ： from 2x+1 The number generated
The second category ： from 3x+1 The number generated
Then open two queues q2 And q3, Stored separately by 2x+1 and 3x+1 The resulting number . The numbers in these two queues must be monotonically increasing .
Constantly compare the head of the two queues , Out of line smaller value , The number thus obtained is monotonic . The number of the heads of the two queues may be the same , There is only one number in the set , In this case, two queues leave the queue at the same time , But in the ascending sequence, only 1 A digital . The... In the ascending sequence n Number , Namely Blah Number in the data set n Number .
specific working means ：
Start by entering the base a Generate 2a+1 And 3a+1, Join the team separately q2 And q3 in . At this time, the count is 1.
The two line-up heads are compared , Which number is smaller , Which number will be out of the team . If equal , At the same time .
Set the number just out of the team to a, Count up 1, And will 2*a+1,3*a+1 Join the team separately .
The count increases to n when , here a The value is Blah No. in the data set n Small numbers .

【 Solution code 】

How to write it 1： Using arrays and expressions to implement queues

#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: Two queues  h,t The head and tail pointers of the two queues 
int main()
{
    
    while(scanf("%d %d", &a, &n) != EOF)
    {
    
        h_2 = t_2 = h_3 = t_3 = 0;// Clear two queues 
        int count = 1;//count Count 
        q2[++t_2] = 2*a + 1;// The team 
        q3[++t_3] = 3*a + 1;
        while(count < n)
        {
    
            if(q2[h_2+1] < q3[h_3+1])// Team leader comparison 
                a = q2[++h_2];// queue 2 Out of the team 
            else if(q2[h_2+1] > q3[h_3+1])
                a = q3[++h_3];// queue 3 Out of the team 
            else// Two equal , All out of the team 
            {
    
                a = q2[++h_2];
                ++h_3;
            }
            q2[++t_2] = 2*a + 1;// The team 
            q3[++t_3] = 3*a + 1;
            count++;
        }
        printf("%d\n", a);
    }
	return 0;
}

How to write it 2： Use 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>();// Clear queue  
		q3 = queue<int>();
		for(int i = 2; i <= n; ++i)// Please i Small value , The initial conditions a It's No 1 Small value  
		{
    
			q2.push(2*a+1);
			q3.push(3*a+1);
			if(q2.front() > q3.front())// If 3x+1 The head of the queue is smaller  
			{
    
				a = q3.front();
				q3.pop();
			}
			else if(q2.front() < q3.front())// If 2x+1 The head of the queue is smaller 
			{
    
				a = q2.front();
				q2.pop();
			}
			else
			{
    
				a = q2.front();
				q2.pop();
				q3.pop();
			}
		}
		cout << a << endl;
	} 
    return 0;
}