消减整数
题目链接:nowcoder 219038
到主站看:https://blog.csdn.net/weixin_43346722/article/details/116171958
题目大意
给你一个数,然后你可以从减 1 开始,接着每次减的要么跟上一次一样,要么是它的两倍,问你最少把减多少次才能把它减到 0。
思路
这道题我们考虑用贪心来做。
那它每次减的可以跟原来一样,也可以翻倍。
那为了让我们减的次数最小,我们肯定是能翻倍就翻倍啊。
那怎么看能不能翻倍呢?
由于你翻倍之后至少都要减它,你要刚好减到 0,就是它剩下的数是它的倍数。
那就可以了,直接贪心就可以了。
代码
#include<cstdio> #define ll long long using namespace std; int T; ll h, ans, two; int main() { scanf("%d", &T); while (T--) { ans = 0; two = 1; scanf("%lld", &h); while (h) { h -= two;//减 ans++;//统计次数 if (h % (2 * two) == 0) two *= 2;//能减两倍的就减两倍 } printf("%d\n", ans); } return 0; }