1 条题解
-
-1
这是一道很简单的题,按题意模拟即可
首先看题,题目告诉我们要用队列
解决这道问题,我们只需要解决几个问题
1.如何维护这个集合的加入操作?
2.如何实现找到第n小的数?
对于第1个问题,很显然,用队列的弹入,弹出操作即可
对于第2个问题,也很显然,优先队列不断维护最小值的操作,可以满足
那么接下来看代码吧
#include<bits/stdc++.h> using namespace std; priority_queue<int,vector<int>,greater<int> >k;//小根堆 bool vis[100000005];//开哈希数组避免重复 int main(){ int a,n; scanf("%d%d",&a,&n);//输入 k.push(a);//队列初始化 int s; for(int i=1;i<n;i++){//维护n-1次 s=k.top();//取出最小数 k.pop(); if(vis[((s<<1)|1)]==0)k.push((s<<1)|1);//如果没有重复,就弹入 vis[((s<<1)|1)]=1;//标记 if(vis[(3*s+1)]==0)k.push(3*s+1);//同理 vis[(3*s+1)]=1; //cout<<s<<endl;调试 } printf("%d\n",k.top());//由于维护n-1次,维护结束后堆顶就是第n小的数 return 0; }
- 1
信息
- ID
- 355
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 49
- 已通过
- 38
- 上传者