队列之blah集合

时间:2023-02-13 04:18:04

  做了一个NOI上面的问题,叫blah集合,以a为基数,则2x+1和3x+1都在集合中,且集合中全部元素都由此计算得来。a∈[1,50],问升序排列后第n(n∈[1,1000000])个元素是多少。以输入示例a=1,n=100,b[n]=418为例:

集合中第一个元素(基数)为1,
      1  3  4  7 10 9 2x+1: 3  7  9 15 21 19…… 3x+1: 4 10 13 22 31 27……

依次计算时会发现每1个数据会变为2个,这些数又会发生交叉。题目需要得到升序后第n个,我们如果先计算再排序一定会超时的,所以我们需要分别把2x+1和3x+1存储起来,然后取之前存储的较小的输出出来,队列很适合这项工作:

#include<iostream>
#include<queue>
typedef unsigned long long uint64;
using namespace std;
uint64 blah(int base,int maxid){
int curval=base,curid=;
queue<uint64> x2,x3;
x2.push(curval*+);
x3.push(curval*+);
while(maxid!=curid){
if(x2.front()==x3.front()){
curval=x2.front();
x2.pop();
x3.pop();
}else if(x2.front()<x3.front()){
curval=x2.front();
x2.pop();
}else{
curval=x3.front();
x3.pop();
}
x2.push(curval*+);
x3.push(curval*+);
curid++;
}
return curval;
}
int main(){
int base,maxid;
while(true){
cin>>base>>maxid;
cout<<blah(base,maxid)<<endl;
}
}

不过遗憾的是,这份代码超时了,虽然它在我的计算机上计算得到结果是瞬间的事情。那么问题在哪呢?只能说可能出现在对front和pop的调用耗时上,当然也可能有内存分配方面的耗时。好吧,我们避免这些调用和重复的初始化——用数组来模拟一下队列:

#include<iostream>
typedef unsigned long long uint64;
using namespace std;
uint64 x2[],x3[];
uint64 blah(int base,int maxid){
int curval=base,curid=,x2id=,x3id=,x2cnt=,x3cnt=,x2val,x3val;
x2[x2cnt]=curval*+;
x3[x3cnt]=curval*+;
while(maxid!=curid){
x2val=x2[x2id];
x3val=x3[x3id];
if(x2val==x3val){
curval=x2val;
x2id++;
x3id++;
}else if(x2val<x3val){
curval=x2val;
x2id++;
}else{
curval=x3val;
x3id++;
}
x2[++x2cnt]=curval*+;
x3[++x3cnt]=curval*+;
curid++;
}
return curval;
}
int main(){
int base,maxid;
while(scanf("%d %d",&base,&maxid)!=EOF){
printf("%llu\n",blah(base,maxid));
}
}

这份代码就以很短的时间通过了测试。