当前位置:   article > 正文

Contest3143 - 2021级新生个人训练赛第36场_B: 数字游戏_小明和佳佳在玩一个默契游戏。他们各说一个正整数,小明说的是 ,佳佳说的是 ,如果

小明和佳佳在玩一个默契游戏。他们各说一个正整数,小明说的是 ,佳佳说的是 ,如果

  1. //
  2. 问题 B: 数字游戏
  3. 时间限制: 1.000 Sec 内存限制: 512 MB
  4. 题目描述
  5. 有一天,小明给佳佳出了一道题,
  6. 给出一个正整数n,佳佳可以进行如下三种操作:
  7. 1、使n减去1
  8. 2、如果n是2的倍数,使n除以2
  9. 3、如果n是3的倍数,使n除以3
  10. 问佳佳最少可以通过几步操作,将n变为0
  11. 为了考验佳佳的知识水平,小明给出了T个数字n1,n2,…,nT,让佳佳对每个数字都给出答案。然而佳佳一心只想着晚上吃啥,想让聪明的你来帮助他解决这个问题,并答应解决后请你吃饭,于是你义不容辞地接下了这个任务。
  12. 输入
  13. 第一行一个正整数T,表示总共有T个数字;
  14. 接下来T行,每行一个正整数ni
  15. 输出
  16. 共T行,每行一个数字,第i行为对于ni的答案。
  17. 样例输入 Copy
  18. 2
  19. 7
  20. 10
  21. 样例输出 Copy
  22. 4
  23. 4
  24. 提示
  25. 【样例解释】
  26. 7->6->2->1->0
  27. 10->9->3->1->0
  28. 【数据范围】
  29. 对于40%的数据,T≤10,ni≤30
  30. 对于70%的数据,T≤20,ni≤1000
  31. 对于100%的数据,T≤20,ni≤1000000

  1. //
  2. 4 -> 3 -> 1 -> 0
  3. 4 -> 2 -> 1 -> 0
  4. 5 -> 4!!! dp

  1. //
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. // 1<=ni<=1000000
  5. const int MAXN=1e6+7;
  6. int dp[MAXN+11]; // +11
  7. void solve()
  8. {
  9. int i;
  10. dp[0]=0; dp[1]=1; // init
  11. for( i=2;i<=MAXN;i++ )
  12. {
  13. dp[i]=dp[i-1]+1; // +1
  14. if( i%3==0 ) dp[i]=min( dp[i],dp[i/3]+1 );
  15. if( i%2==0 ) dp[i]=min( dp[i],dp[i/2]+1 );
  16. }
  17. }
  18. int main()
  19. {
  20. int t,n; solve();
  21. scanf("%d",&t);
  22. while( t-- )
  23. {
  24. scanf("%d",&n);
  25. printf("%d\n",dp[n]);
  26. }
  27. return 0;
  28. }

  1. //
  2. find:
  3. 01 手算模拟 发现特征 选用算法
  4. 02 防止越界 +11

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/884193
推荐阅读
相关标签
  

闽ICP备14008679号