谦虚数字

题目 谦虚数字

思路分析

与超级丑数变化的地方在于 1不是第一个丑数了

但其他数还是得从1变化而来

代码实现

#include<bits/stdc++.h>

using namespace std;

struct Data{

    int v,p,k;//当前值 质数 索引

    bool operator<(const Data& other)const{

        return v>other.v;

    }

};

int n,k;

int main()

{

    cin>>k>>n;

    n++;//1不是谦虚数字仅用于生成其他谦虚数字

    vector<int> uglynums(1,1);//存储谦虚序列初始值1

    priority_queue<Data> heap;//下一个可能的谦虚数字

    while(k--){

        int p;cin>>p;

        heap.push({p, p, 0});

    }

    while(uglynums.size()<n){

        auto minval = heap.top().v;

        uglynums.push_back(minval);//这个数字加入谦虚数字序列

        //弹出所有重复minVal 移动指针（添加新数）

        while (!heap.empty() && heap.top().v == minval){

            auto ugly=heap.top();

            heap.pop();

            heap.push({ugly.p * uglynums[ugly.k + 1], ugly.p, ugly.k + 1});

        }

    }

    cout<<uglynums.back();

    return 0;

}

同类题型

视频讲解

⬅️ 蚯蚓 🏠 00-刷题理模型 ➡️ 超级丑数