最少砝码 Java解决

2744557306

问题描述】
2 [1 o, B6 p' w* h你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
& {1 w" r+ f; Z8 f0 T5 w6 O+ B那么这套砝码最少需要包含多少个砝码？
, j! F6 z* F$ Y- Z% }  P! l# T注意砝码可以放在天平两边。

4 K# T1 M  ^% G; B1 O, S【输入格式】
9 o, I9 J! }* \8 C3 [# s: T输入包含一个正整数 N。

【输出格式】
输出一个整数代表答案。
: N; B/ t" b2 R3 I$ ]7 R; B
0 q" V8 @0 F! ]【样例输入】
6 s! Q+ G) g+ }+ [7
2 M' I% `" {; o: Z# F, g
  Z9 n2 B7 C5 F4 M【样例输出】
3

【样例说明】
8 H- ~+ t& f+ `) M3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
1 = 1；
( D# g0 C; L3 `6 E7 v2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
5 b) ?$ q4 R' F) [% w4 = 4；
0 s+ ]9 C: ]! V: P$ `5 = 6 − 1；
6 = 6；
6 j3 x0 K3 L. ?9 {7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   ! w5 \) n! s/ e, m; o' @1 N! A
2. public class Main {  1 s0 F3 x\" v2 i& ?\" s& h: ]( C/ E% h
   
3.     public static void main(String[] args) {  ) u+ G0 L, D5 Z9 e0 V
   
4.         int n = new Scanner(System.in).nextInt();    6 y! V% |& c& P9 ~( j
   
5.         int maxWeight = 1, minCnt = 1;  ( P1 ^+ I5 ~2 b0 T& S( J
   
6.         while (maxWeight < n) {  \" f- s& U2 j$ h3 ^+ o# W4 a4 U
   
7.             maxWeight = maxWeight * 3 + 1;  
   1 Q\" Q6 W! R; F, L* b
8.             minCnt++;  
   5 g. R3 _\" M$ W' o# i' o+ w
9.         }  \" [: _. l- ]6 k/ I& `
   
10.         System.out.println(minCnt);  , \& H0 b' C6 `
    
11.     }  
    . Q' x7 y/ g\" R9 F' ~
12. }, `, d, F' f\" T5 J* Y+ i
    

复制代码

题解
! o. _/ O( _6 F+ ]. l如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
( b2 B1 l/ F% E! g7 }+ _因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围

另 n + 1 = k - n k = 2n + 1
1 v8 v( e8 |4 J6 A$ H5 e那么x + 1可以控制的最范围就是[1, 3n + 1]
% g0 v. k" ^! s0 |