HDU 1058 优先队列or堆
2024-08-28 08:22:48
本来应当是一道优先队列或者堆的题 因为每个数都应该是已经得到的数*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]);
}
}
最新文章
- ASP.NET MVC+EF框架+EasyUI实现权限管理系列(24)-权限组的设计和实现(附源码)(终结)
- TopFreeTheme精选免费模板【20130701.特别版】
- BeanDefinition的Resource定位——3
- tomcat之JNDI数据源配置
- MySQL协议分析
- Linux Shell编程（5）——shell特殊字符（下）
- linux Bash bug修复记录
- WebView.destroy() called while still attached 的解决的方法
- boost之program_options库，解析命令行参数、读取配置文件
- Linq 实现sql中的not in和in条件查询
- linux的软件安装方式总结
- bootstrap概述
- Http状态信息
- ElasticSearch6.5.0 【安装IK分词器】
- SQL Server 性能优化实战系列(一)
- 7.15python进程锁
- Asp.net core 学习笔记 ( OData )
- java Random.nextInt()方法
- python with 语句妙用
- 如何修改路由器的登录IP地址？