问题描述】
1 u9 i1 z! t7 u8 Y$ l. v, p你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
5 f4 d7 {! Y+ Z2 `3 {3 L1 S注意砝码可以放在天平两边。

【输入格式】
, N0 x' p0 G$ s6 t3 j& x& R5 _输入包含一个正整数 N。

【输出格式】
5 Z- e5 k7 J+ {' t  m! C( s输出一个整数代表答案。
0 `. \$ c: U1 \1 k/ |% ]0 p) x3 |
4 v( c) e! D1 L  Z2 R【样例输入】
7
  j: w; }8 N4 z5 U2 v2 d
【样例输出】
3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
  n4 I3 _7 i) Q5 = 6 − 1；
0 X( z# {( d9 U- Q7 U: X6 = 6；
7 = 1 + 6；
4 Y( K( W5 R% L6 V* }0 {/ G) J少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   , {. p& a& V+ t' o) b5 F
2. public class Main {  0 C) Q6 E# Q% n* Z
   
3.     public static void main(String[] args) {  
   $ T! B+ |# {0 f
4.         int n = new Scanner(System.in).nextInt();   
   4 c3 H( Q# G, P; w
5.         int maxWeight = 1, minCnt = 1;  
   5 L) d; z! y; v
6.         while (maxWeight < n) {  
   \" \3 u6 \# t* {! M9 ~& W5 O
7.             maxWeight = maxWeight * 3 + 1;  
   ' B% ~! b; I, e, T+ j
8.             minCnt++;  * A  Y8 I' L5 _
   
9.         }  % J' n8 ^' L% q4 w5 {\" e# E
   
10.         System.out.println(minCnt);  
    4 K) z3 m6 c7 E# e+ _( F/ J
11.     }  , `4 Z( |; f8 |1 E  O* Y, U
    
12. }
    : d2 L  [4 ^: R; R3 A$ B

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
2 D) A0 k1 C( U1 q1 T. }此时我们想扩大区间范围就只可以增加砝码
6 T5 Y1 _  [& z+ o假设增加的砝码重量为 k
( D8 r4 k+ }6 O0 V% D因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
. B% [$ C( o9 ~
& p' D) ~. p. S让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
6 p  y" u+ D! V6 h, P
另 n + 1 = k - n k = 2n + 1
$ P9 L4 c# l  ]3 m) C" @2 W那么x + 1可以控制的最范围就是[1, 3n + 1]
# k- r' J0 p3 C+ V  ~

2 \/ s9 }6 _3 y; V+ j
& L) M, _' v1 o6 h' Y