第十二届蓝桥杯省赛-最少砝码C++

用贪心的思想来解决这个问题：尽可能在增加砝码时使得砝码的重量最大。

要称重量为 1，需要砝码 1

重量为 2，增加砝码 3（使增加的砝码尽可能的大，所以不是 1 和 2 ）

1 3 可以同时称 ‘1’=1，‘2’+1=3，‘3’=3，‘4’=3+1 ；

所以下一个是5，增加砝码 9（尽可能的大）

1 3 9 可以同时称（除去 1 和 3 能称的）：

‘5’+3+1=9，‘6’+3=9，‘7’+3=9+1，‘8’+1=9，‘9’=9

‘10’=9+1，‘11’+1=9+3，‘12’=9+3，‘13’=1+3+9

下一个是14，增加砝码几呢？

n - w

1 - 3

2 - 1 3

5 - 1 3 9

大胆推测一下（或者接着演算），下一个增加的砝码是 9*3=27

由上面演算可知增加的砝码每次乘以三，

可测量的数字为上一轮的 n+w；

很容易推出公式

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <cstdio>
#include <map>

#define LEN(array) ((sizeof(array)) / (sizeof(array[0])))
#define mo 1e9 + 7
#define ll long long int

using namespace std;

int main(void){
    int n;
    cin >> n;
    int weight = 1;
    int count = 1;
    int total = 1;
    while (total < n){
        count++;
        weight *= 3;
        total += weight;
       
    }
    cout << count << endl;
    return 0;

}