1 条题解

  • -1
    @ 2023-3-17 21:02:03

    这是一道很简单的题,按题意模拟即可

    首先看题,题目告诉我们要用队列

    解决这道问题,我们只需要解决几个问题

    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
    上传者