最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
5 Q: W1 H. x; _4 ]7 @6 Z( S那么这套砝码最少需要包含多少个砝码？
+ y. ~$ A" U7 z/ Z- F注意砝码可以放在天平两边。
! a7 s) J" B3 Z
! k+ h" l1 x/ F) D. g7 J【输入格式】
输入包含一个正整数 N。

$ `& \% F. A" k7 i【输出格式】
输出一个整数代表答案。

【样例输入】
$ P; b1 \* x/ g& m" G8 f) y7
8 p3 e# _# U, Y: t& c3 Z+ ?! T
' t& q# C2 M5 p7 }2 P: w【样例输出】
3
) v! L% T2 p: ]0 e0 M9 h
0 E: G5 b* C$ T" ^1 j5 F% y【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
3 |! d4 [5 v. b( \) R2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
  K7 l0 ]# J1 P9 `5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  $ ^! f5 G/ E/ v% Q: Q; Q
   
2. public class Main {  ! w. b$ ]- Y2 B
   
3.     public static void main(String[] args) {  ; v3 |2 a4 D: g* }' C
   
4.         int n = new Scanner(System.in).nextInt();    ! X$ R$ h2 b) m\" i, P, K2 P
   
5.         int maxWeight = 1, minCnt = 1;  
     ]\" _) K! i4 w+ l
6.         while (maxWeight < n) {  ( y$ D( }5 v$ V
   
7.             maxWeight = maxWeight * 3 + 1;  1 t+ w( D3 |& F- J
   
8.             minCnt++;  5 {, A1 r\" c! G! E
   
9.         }  0 r5 t/ _5 E3 @; \6 S) C
   
10.         System.out.println(minCnt);  
    \" e9 k9 W. |/ g\" _* O' u! R0 B
11.     }  
    ( D: I0 @8 c* m6 U* v+ V4 m
12. }# V\" D\" z\" J+ `9 {; D
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
/ R* I( C- C8 x此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
( m8 o1 c" X" \& l! e, v因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
- Y; G/ P8 [4 B+ A; i7 @2 u/ |所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
0 L" K2 n; c' a
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
6 i7 c7 A# m! G# r  v
另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]


' H! C, g8 K: F7 B