51nod 1010 只包含因子2 3 5的数

2023-11-23 23:30:04

题目链接：http://class.51nod.com/Challenge/Problem.html#problemId=1010

一、题目描述

K的因子中只包含2 3 5。满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。

所有这样的K组成了一个序列S，现在给出一个数n，求S中 >= 给定数的最小的数。

例如：n = 13，S中 >= 13的最小的数是15，所以输出15。

输入描述

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000) 第2 - T + 1行：每行1个数N(1 <= N <= 10^18)

输出描述

共T行，每行1个数，输出>= n的最小的只包含因子2 3 5的数。

样例输入

样例输出

二、思路描述

尽管N的范围达到1e18，但实际符合条件的数字却并不多，不到15000个。

这点很关键，所以我们可以预先处理出1e18以内，所有符合条件的数字。

获取符合条件的数字的方法很多，我们介绍一下如何用优先队列解决这个问题。

我们将2,3,5放入优先队列，每次从队列中取出最小的数，把这个数分别乘以2,3,5后，再放回到优先队列中。

这样就可以得到所有的符合条件的数。

需要注意的是，有些数字会重复出现，例如：60，有可能通过12 * 5得到，也可能通过20*3,30*2得到，需要去掉重复出现的。

具体方法是在弹出队列时如果发现与上一个数相同，则不再处理。

在这里我们也复习一下怎么在优先队列里找到最小数：

只要是这么写的，就说明q这个优先队列是从小到大排列的：

priority_queue <int,vector<int>,greater<int> > q;

现在给优先队列的基本操作（只在本题中使用的基本操作）：

priority_queue <long long, vector <long long>, greater <long long> > que; 定义一个从小到大排列的优先队列

que.push(1); 往优先队列que中存入1这个数

que.size() 返回que里元素个数

que.top() 这个只能在优先队列里使用，不能再普通队列里使用。

　　　　　　　　　如果是从小到大排列的优先队列。那么第一个肯定是最小的，最后一个是最大的

　　　　　　　　　那么返回第一个数字（在这道题里是返回最小的）

在这里我们也复习一下什么是vector不定长数组

vector不定长数组就是一个数组，只不过没有长度限制。

但是vector不定长数组的操作（例如插入或删除一个数）都和普通数组不一样

现在给vector的基本操作（只在本题中使用的基本操作）：

vector <long long> value; 定义一个不定长数组value

value.push_back(v); 往value不定长数组中插入一个数v

value.begin() value开始的下标

value.end() value结束的下标

　　在这里我们也复习一下什么是lower_bound()和upper_bound()。

　　lower_bound是查找一个数组中大于等于一个数的最小值。

　　以下是规定写法：

　　lower_bound(开始的下标，结束的下标，查找的那个数) - 数组名

　　————————————————————————————————

　　upper_bound是查找一个数组中大于一个数的最小值

　　以下是规定写法：

　　upper_bound(开始的下标，结束的下标，查找的那个数) - 数组名

　　在这道题中我们可以利用lower_bound()函数来求出vector不定长数组中大于等于n的最小值

三、代码

#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
long long a[1000000], cnt, t, n[10010], maxnumber=1e18, tmp;
priority_queue <long long, vector <long long>, greater <long long> > que;
vector <long long> values;

void pre(){
    que.push(1);
    while(que.size() > 0){//只要里面还有数 
        tmp = que.top();//tmp=最小数 
        if(tmp > maxnumber){//如果这个最小数太大了，不算了 
            break;
        }
        while(que.size() > 0 && tmp == que.top()){//去掉重复数字并且把最小数字弹出去 
            que.pop();
        }
        if(tmp > 1){ 
            values.push_back(tmp);
        }
        que.push(tmp*2);//把最小的数乘上2后也放进优先队列里 
        que.push(tmp*3);//把最小的数乘上3后也放进优先队列里 
        que.push(tmp*5);//把最小的数乘上5后也放进优先队列里 
    }
}

int main(){
    sort(a,a+cnt);
    cin >> t;
    for(int i = 0;i < t;i++){
        cin >> n[i];
    }
    pre();
    for(int i = 0;i < t;i++){
        cnt = values[lower_bound(values.begin(), values.end(), n[i]) - values.begin()];
        cout << cnt << endl;
    }
    return 0;
}

码农公寓