这题用堆的思路来模拟。因为不会用堆去重所以只是借鉴思路来模拟。
这题还有的就是序数词的输出,个位是1,2,3,十位是1的时候进行特判。
兼顾时间复杂度所以在预处理中打个表。
#include<bits/stdc++.h> using namespace std; const int N=5850; int dp[N],a,b,c,d,n; void get_ans() { dp[1]=1; a=b=c=d=1; for(int i=2;i<=5843;i++) { dp[i]=min(min(dp[a]*2,dp[b]*3),min(dp[c]*5,dp[d]*7)); if(dp[i]==dp[a]*2) a++; if(dp[i]==dp[b]*3) b++; if(dp[i]==dp[c]*5) c++; if(dp[i]==dp[d]*7) d++; } } void print(int n) { if(n%100!=11&&n%10==1) printf("The %dst humble number is %d.\n",n,dp[n]); else if(n%100!=12&&n%10==2) printf("The %dnd humble number is %d.\n",n,dp[n]); else if(n%100!=13&&n%10==3) printf("The %drd humble number is %d.\n",n,dp[n]); else printf("The %dth humble number is %d.\n",n,dp[n]); } int main() { get_ans(); while(~scanf("%d",&n)) { if(!n) break; print(n); } return 0; }