这题找规律不要太简单(找不到规律那就 gg 了…),其实说是贪心策略更高大上
找规律:
一个砝码:要表示出小于等于n的所有重量,很明显n只能等与1,即一个砝码符合要求的重量只能是1;
两个砝码:要表示出最多的连续重量,基于上一个砝码的基础上去探讨,一个砝码表示不出来的最小的数是2,基于
贪心的思想,让第二个砝码重量取3,这样3-1=2,3=3,3+1=4,可以表示1~4任意的重量(因为是贪心,所以
第二个砝码的最优选择是3,如果选1或者是2,都没有3的解优秀);
三个砝码:两个砝码表示不出来的最小重量是5,基于贪心让第四个砝码重量-能表示出来的最大重量(此例中是4)=
表示不出来的最小重量(此例中是5),所以第三个砝码重量取9,很容易可以得出,1,3,9,三个砝码能表示
出1~13中任意的重量;
四个砝码:相信你已经知道要选哪四个重量了,没错就是1,3,9,27 (因为27-13=14)
......
规律就是:下一个砝码重量 - 当前砝码能表示出来的最大重量 = 当前砝码表示不出来的最小重量
在简单点就是,砝码的选择是 3^0 , 3^1 , 3^2 , 3^3 ,3^然后自己统计一下数量,计算一下表示出来的
最大重量(这个就简单了)
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n;
cin>>n;
int a=1,t=1,sum=1; // a :砝码数量 t :砝码的重量 sum :能表示出来的最大重量
while(1)
{
if(sum>=n)
{
cout<<a<<endl;
break;
}
t*=3; //砝码重量1,3,9,27...
sum+=t; //可以表示的最大重量1,4,13
a++; //砝码数量
}
return 0;
}
牛啊
有点东西的
这个找规律实在是太强了
%%%%%%%%%%%%%%%%%
有点小牛
niu
牛