2612: 蓝桥杯2021年第十二届省赛真题-最少砝码(C++)

解题思路:

//思路：贪心算法:初始砝码重量一定为1，利用贪心的思路，我们希望每当当前砝码称重范围不足时，加入的那个砝码将称重范围最大程度上得扩大

//当n==1时,所加砝码重量为1,当前砝码为1，总重量1

//当n==2时,所加的砝码重量为1+2=3时可以最大化扩大范围，当前砝码为1，3，总重量为4

//当n==3时,所加砝码重量为4+5=9时可以最大化扩大范围，当前砝码为1，3，9，总重量13

//依次类推，我们可以知道后面依次加入的砝码的重量为13+14=27，40+41=81……

注意事项:

参考代码:

#include<iostream>
using namespace std;
typedef long long ll;
int main() {
	ll n,max;//max表示当前砝码能称出的最大范围
	cin >> n;
	int num=2;//放入重量1，3两个砝码，目前可称出的范围为1~4
	max = 4;
	if (n == 1) cout << 1;
	else {
		while (1) {
			if (n <= max) {
				cout << num;
				break;
			}
			else {
				num += 1;
				max += (max * 2 + 1);
			}
		}
	}
	return 0;
}