4.5算法之动态规划 1249:Humble Numbers 优先级队列

http://noi.openjudge.cn/ch0405/1249/

思路

取出队头,遍历乘四放入队列,即可保证当前队头为最小值

源码

//
//  1249.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int m[4]={2,3,5,7};
priority_queue<long long,vector<long long>,greater<long long>> q;
int main(){
    q.push(1);
    int idx = 0;
    int i;
    long long pre = 0;
    while(cin >> i){
        if(i == 0){
            break;
        }

        while(idx<i){
            while(q.top()==pre){
                q.pop();
            }
            pre = q.top();
            idx++;
            for(int i = 0;i < 4;++i){
                q.push(pre*m[i]);
            }
        }
        if(i%100>=10&&i%100<=20)
            printf("The %dth humble number is %lld.\n",i,pre);
        else if(i%10==1)
            printf("The %dst humble number is %lld.\n",i,pre);
        else if(i%10==2)
            printf("The %dnd humble number is %lld.\n",i,pre);
        else if(i%10==3)
            printf("The %drd humble number is %lld.\n",i,pre);
        else
            printf("The %dth humble number is %lld.\n",i,pre);
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注