首页 > 代码库 > 队列之blah集合
队列之blah集合
做了一个ＮＯＩ上面的问题，叫ｂｌａｈ集合，以ａ为基数，则２ｘ＋１和３ｘ＋１都在集合中，且集合中全部元素都由此计算得来。ａ∈［１，５０］，问升序排列后第ｎ（ｎ∈［１，１００００００］）个元素是多少。以输入示例ａ＝１，ｎ＝１００，ｂ［ｎ］＝４１８为例：
集合中第一个元素（基数）为１，
１ ３ ４ ７ １０ ９２ｘ＋１： ３ ７ ９ １５ ２１ １９……３ｘ＋１： ４ １０ １３ ２２ ３１ ２７……
依次计算时会发现每１个数据会变为２个，这些数又会发生交叉。题目需要得到升序后第ｎ个，我们如果先计算再排序一定会超时的，所以我们需要分别把２ｘ＋１和３ｘ＋１存储起来，然后取之前存储的较小的输出出来，队列很适合这项工作：
#include<iostream>#include<queue>typedef unsigned long long uint64;using namespace std;uint64 blah(int base,int maxid){ int curval=base,curid=1; queue<uint64> x2,x3; x2.push(curval*2+1); x3.push(curval*3+1); 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*2+1); x3.push(curval*3+1); curid++; } return curval;}int main(){ int base,maxid; while(true){ cin>>base>>maxid; cout<<blah(base,maxid)<<endl; }}
不过遗憾的是，这份代码超时了，虽然它在我的计算机上计算得到结果是瞬间的事情。那么问题在哪呢？只能说可能出现在对ｆｒｏｎｔ和ｐｏｐ的调用耗时上，当然也可能有内存分配方面的耗时。好吧，我们避免这些调用和重复的初始化——用数组来模拟一下队列：
#include<iostream>typedef unsigned long long uint64;using namespace std;uint64 x2[1000000],x3[1000000];uint64 blah(int base,int maxid){ int curval=base,curid=1,x2id=0,x3id=0,x2cnt=0,x3cnt=0,x2val,x3val; x2[x2cnt]=curval*2+1; x3[x3cnt]=curval*3+1; 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*2+1; x3[++x3cnt]=curval*3+1; curid++; } return curval;}int main(){ int base,maxid; while(scanf("%d %d",&base,&maxid)!=EOF){ printf("%llu\n",blah(base,maxid)); }}
这份代码就以很短的时间通过了测试。
队列之blah集合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。