本文主要是介绍蓝桥集训之谦虚数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓝桥集训之谦虚数字
-
核心思想：多路归并
- 在每个质数后开一个队列 存所有从该数得来的谦虚数
- 用优先队列 保证每个队列中有且仅有一个数在优先队列中比较大小
- 用对组标记 每个谦虚数的来历(队列编号)
- 每次取出优先队列头元素 分别跟质数相乘 再放入各自队列
- 若取出队列a的元素 则把队列a头元素再放入优先队列
-
#include<iostream>#include<algorithm>#include<cstring>#include<queue>#include<vector>using namespace std;const int K = 100;typedef long long LL;typedef pair<LL,int> PLI;int p[K]; //每个质数queue<LL> can[K]; //每个质数的队列priority_queue<PLI,vector<PLI>,greater<PLI>> pq; //优先队列int k,n;int main(){cin >> k >> n;for(int i=0;i<k;i++){cin>>p[i];pq.push({p[i],i}); //把所有质数先放入优先队列}LL res=0;for(int i=0;i<n;i++){auto t = pq.top();pq.pop();LL a = t.first;int b = t.second;res = a; //定答案for(int j=b;j<k;j++) //从当前队列b开始往后乘 不乘前面的(重复){can[j].push(a * p[j]); //新的谦虚数if(j==b) //此时优先队列中没有b队列的元素{pq.push({can[j].front(),j}); //把队列b头元素放入优先队列can[j].pop();}}}cout<<res;}
这篇关于蓝桥集训之谦虚数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
