本来应当是一道优先队列或者堆的题 因为每个数都应该是已经得到的数*2 *3 *5 *7而得到的 但是 2*7 大于 3*2 这就必须保证每次取得都是没有拿过的最小的数
但是它主动降低难度在样例里卖了个萌 n的范围是1~5842 而第5842在样例里给出了..所以我们在取出一个数 求出它的*2 *3 *5 *7的时候做一下判断 如果大于最后一位就直接break 因为相乘的顺序在 可以省一点时间
在判断某个数是否出现过的时候 开不出那么大的vis数组 所以直接for循环从ans数组中寻找 所幸没有超时QAQ
尤其需要注意的是题目的思考并不难 但是输出的英语用法是坑
1 2 3 分别是 first second third 所以缩写的是 st nd rd
21 22 23 等 是 twenty - first twenty - second twenty- third 等 它们的缩写都是 st nd rd
但是11 12 13 不是.. 它们的第次缩写都是 th
(我的输出代码写得判断很麻烦..因为我懒得改..)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<queue>
#include<iostream>
using namespace std;
long long int e[6050];
int w;
bool find(long long int x)
{
for(int i=0;i<w;i++)
{
if(e[i]==x)
return true;
}
return false;
}
void init()
{
w=0;
queue<long long int >q;
q.push(2);
q.push(3);
q.push(5);
q.push(7);
e[w++]=1;
e[w++]=2;e[w++]=3;e[w++]=5;e[w++]=7;
while(!q.empty())
{
long long int z=q.front();q.pop();
/* if(w==5842)
return ;*/
for(int i=0;i<4;i++)
{
long long int x=z;
///if(x> 2000000000)continue;
if(i==0)
{
x*=2;
if(x> 2000000000)
break;
if(!find(x))
{
e[w++]=x;
q.push(x);
}
}
else if(i==1)
{
x*=3;
if(x> 2000000000)
break;
if(!find(x))
{
e[w++]=x;
q.push(x);
}
}
else if(i==2)
{
x*=5;
if(x> 2000000000)
break;
if(!find(x))
{
e[w++]=x;
q.push(x);
}
}
else if(i==3)
{
x*=7;
if(x> 2000000000)
break;
if(!find(x))
{
e[w++]=x;
q.push(x);
}
} }
} }
int main(){
init();
int n;
sort(e,e+w);
while(~scanf("%d",&n))
{
if(n==0)
break;
if(n==11)
printf("The 11th humble number is ");
else if(n==12)
printf("The 12th humble number is ");
else if(n==13)
printf("The 13th humble number is ");
else
{
if(n%10!=1&&n%10!=2&&n%10!=3)
{
printf("The %dth humble number is ",n);
}
else if(n%10==1&&n%100!=11)
{
printf("The %dst humble number is ",n);
}
else if(n%10==2&&n%100!=12)
{
printf("The %dnd humble number is ",n);
}
else if(n%10==3&&n%100!=13)
{
printf("The %drd humble number is ",n);
}
else
printf("The %dth humble number is ",n);
}
printf("%I64d.\n",e[n-1]);
}
}