最少砝码 Java解决

2744557306

问题描述】
+ r8 `4 v; x. {+ q, O7 d5 J你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
' R  R) n+ d& ]. x- A+ x5 S/ q那么这套砝码最少需要包含多少个砝码？
$ \- D8 S: E( ~0 |8 x) q8 L+ O( X9 U. e注意砝码可以放在天平两边。
$ Q( D" `+ ^. X! u! \1 O. r
2 ]( L6 w' K" T" r$ W【输入格式】
: e$ N' V8 C" j" z6 v' z, C' E输入包含一个正整数 N。

【输出格式】
1 }' t4 n2 p* A$ W/ _6 u* ~+ |3 D输出一个整数代表答案。
1 c2 A$ C$ E" B2 }$ n9 V' u8 B
% D& ~% T8 i& h1 t8 W0 C% b+ `9 N【样例输入】
% h! K# O' G; y& ^( O1 O" ^7

2 p( u; J* m( T2 y【样例输出】
6 u8 }2 F) l# P9 @; O$ a3

! L) r. w# o9 r" U; v. [% I【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
. s; Z% z5 ^5 x+ K+ a1 = 1；
4 p' l& F# P1 Y7 l7 g2 = 6 − 4 (天平一边放 6，另一边放 4)；
" j: Q$ ~/ U* C. u' l3 = 4 − 1；
4 = 4；
5 R8 {1 [3 V3 K& N5 = 6 − 1；
6 = 6；
; ~4 d0 t  K* ]  C. S" I7 = 1 + 6；
; R% P# t! B) c少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   ! L' w( e5 O8 U) j+ R
2. public class Main {  
   - q7 T  N( Y$ y# b' B+ _; X+ B
3.     public static void main(String[] args) {  
   $ s, y4 ?& c1 f4 S
4.         int n = new Scanner(System.in).nextInt();   
   , h8 ?# I3 a$ U
5.         int maxWeight = 1, minCnt = 1;  
   6 B% w/ `. k2 w\" M
6.         while (maxWeight < n) {  ( V3 T- _; P# u/ x) E
   
7.             maxWeight = maxWeight * 3 + 1;  
   2 r% D, ?3 Q8 S* c+ p2 s, N! ^
8.             minCnt++;  
     z1 B3 [. H) {
9.         }  
   0 E; b. J; S0 n- ^2 O& Q; Y\" D
10.         System.out.println(minCnt);  8 C' S# a\" E0 e, S! I: G9 u9 y1 a
    
11.     }  1 M: _) G8 _: Z0 ^& p4 F& O
    
12. }6 p& t, u+ U, T9 X0 v1 D6 b
    

复制代码

题解
/ c3 a. k+ F" G1 V如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
, ~% J- T3 k0 ^2 o* y此时我们想扩大区间范围就只可以增加砝码
  E" p( f& F' I2 a9 T9 A假设增加的砝码重量为 k
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
7 E8 Q9 K% R5 ]( @
/ R6 y3 v7 F4 E0 ~0 W另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]

) R; _3 }  Q6 I$ L1 Z6 y$ ~