【例2-2】Blah数集
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 287 通过数: 144
【题目描述】
大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对于以a为基的集合Ba定义如下:
(1)a是集合Ba的基,且a是Ba的第一个元素;
(2)如果x在集合Ba中,则2x+1和3x+1也都在集合Ba中;
(3)没有其他元素在集合Ba中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列,第N个元素会是多少?
【输入】
输入包括很多行,每行输入包括两个数字,集合的基a(1≤a≤50))以及所求元素序号n(1≤n≤1000000)。
【输出】
对于每个输入,输出集合Ba的第n个元素值。
【输入样例】
1 100
28 5437
【输出样例】
418
900585
【来源】
No
【算法分析】
可以用两个队列a和b来存放新产生的数,然后通过比较大小决定是否输出,具体方法如下:
(1)令fa和fb分别为队列a和队列b的头指针,它们的尾指针分别为ra和rb。初始时,X=1,fa=fb=ra=rb=1;
(2)将2*x+1和3*x+1分别放入队列a和队列b的队尾,尾指针加1。 即:a[r]←2*x+1,b[r]←3*x+1,r←r+1;
(3)将队列a和队列b的头结点进行比较,可能有三种情况:
(A)a[ha]>b[hb] (B)a[ha]=b[hb] (C)a[ha]<b[hb]
将比较的小者取出送入X,取出数的队列的头指针相应加1。
(4)重复(2),(3)直至取出第N项为止。
【代码实现】
#include<bits/stdc++.h>
using namespace std;
long long int a[1000005],b[1000005],x,fa=1,fb=1,ra=0,rb=0,total=1,n,i;//r头指针,f尾指针
int main()
{while(~scanf("%d%d",&x,&n)){fa=1;fb=1;ra=0;rb=0;total=1;//就是这里,记住第一个对,第二个错,检查清0while (total<n){a[++ra]=(x*2)+1;b[++rb]=3*x+1;if (a[fa]>b[fb]) x=b[fb++];else if (a[fa]<b[fb]) x=a[fa++];else{x=a[fa++];fb++;}total++;}cout<<x<<endl;}return 0;
}