最少砝码 Java解决

2744557306

问题描述】
7 L; P) Z" z- y1 z你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
) V- {, P8 j; F- [2 `那么这套砝码最少需要包含多少个砝码？
3 A7 S/ G" n% O注意砝码可以放在天平两边。
% M0 ~- t7 d3 M" C3 P6 v, e! x
/ k/ m5 f- G/ I. d7 R5 `【输入格式】
. Z6 ]- p( _; y, p- t' j3 Z! ]0 ^输入包含一个正整数 N。

8 K# J* x8 B- |6 {2 k8 }【输出格式】
* M) m# k9 B( `. y* h3 q* l, X输出一个整数代表答案。

8 u2 _+ _0 Y9 q% C9 x, N【样例输入】
7

0 F6 m( ]. k& |# l【样例输出】
3

【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
* l: x4 S( Q9 Q. w1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
* N; f& i/ e7 u# l& {3 = 4 − 1；
4 = 4；
8 k  M/ h0 b- O5 = 6 − 1；
6 = 6；
' Q+ v1 ?1 f# A+ r. W: D! i4 I% w4 b5 E$ g7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  / W( S' _; Y( _9 L! {4 y* [  I# u
   
2. public class Main {  
   % |) y6 z  R# P/ Q0 C7 K
3.     public static void main(String[] args) {  
   1 R9 h& e) G9 U0 g\" f6 F, A' m
4.         int n = new Scanner(System.in).nextInt();    4 |& i# s' E- L4 \; u2 z
   
5.         int maxWeight = 1, minCnt = 1;  
   5 I, C, |. Q% L, E. J
6.         while (maxWeight < n) {  & `' u. c  ^7 t! A8 z. \$ Z: r$ z
   
7.             maxWeight = maxWeight * 3 + 1;  * }8 B+ x2 ^, B1 r% G* I
   
8.             minCnt++;  
   9 ~! H$ O+ g6 ^) ?
9.         }  * ?* |2 O1 t9 h: b
   
10.         System.out.println(minCnt);  : x\" w* `7 O2 n7 P1 K
    
11.     }  + O1 B' ^  C* n\" y% S8 K/ \
    
12. }
      r% b& t5 i/ X1 h1 @+ t3 Y

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
. A& e  @# Z4 U- K! Z8 N因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
8 n# G7 I4 z( i! d' _! Y0 ]
3 L. V+ H9 Y/ c  U2 }另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]
3 N6 i8 B+ k1 T' J0 y


  z: Z8 v  v' E0 H: }+ |