目录

牛客_消减整数_贪心+数学

题目解析

C++代码

Java代码

---

牛客_消减整数_贪心+数学

消减整数 (nowcoder.com)

描述：
        给出一个正整数H，从1开始减，第一次必须减1，每次减的数字都必须和上一次相同或者是上一次的两倍，请问最少需要几次能把H恰好减到0。

输入描述：

第一行给出一个正整数T，1≤T≤10^4

接下来T行，每行一个H，1≤H≤10^9

输出描述：

每行一个正整数代表最少的次数

---

题目解析

贪心 + 数学：

• 尽可能的翻倍。
• 不能无脑翻倍，只能是 2 * cur 的倍数时，才能翻倍。

C++代码

#include <iostream>
using namespace std;int main()
{int T = 0;cin >> T;while(T--){int h = 0;cin >> h;h--;int res = 1, last = 1;int tmp = h, resTmp = 1;while(h > 0){// cout << last << " " << h << endl;if(h - last * 2 >= 0){h -= last * 2;last *= 2;}else if(h - last >= 0){h -= last;}else // 重新计数{h = tmp - 1;tmp--;res = resTmp + 1;resTmp++;}++res;}cout << res << endl;}return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int t = in.nextInt();while(t-- != 0){int h = in.nextInt();int ret = 0, a = 1;while(h != 0){h -= a;ret++;if(h % (a * 2) == 0){a *= 2;}}System.out.println(ret);}}
}