最少砝码 Java解决

2744557306

问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
( a  ], l. Y( [2 Q, c. z注意砝码可以放在天平两边。
$ ~8 R2 M+ \( x
【输入格式】
5 s  x- P6 P2 Y$ _) Q8 q输入包含一个正整数 N。
' s+ i' i2 J  h$ W% M- v6 e! g
【输出格式】
输出一个整数代表答案。

: \; @& r8 }1 Y; |% Z2 o' I, e8 E# |【样例输入】
7

( c$ |6 v0 Q# v) w" _【样例输出】
5 m3 }' A; {2 x3

' Z2 D6 C+ ?. a5 a# H+ x【样例说明】
3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。
5 O  X" _- O5 t: S1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
5 x% g0 W, @5 X( F4 ~4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

1. import java.util.Scanner;  
   % Y! o& }% `/ N9 Q3 {' u) {( c
2. public class Main {  
   - i* @' ]& m7 }% s
3.     public static void main(String[] args) {  3 J4 W! C% j) t* p0 P
   
4.         int n = new Scanner(System.in).nextInt();   
   & |' R2 o! V0 Z$ d' F: M
5.         int maxWeight = 1, minCnt = 1;  
   / o' L. A0 b' h( G. \3 |) I
6.         while (maxWeight < n) {  : `) R! H# i4 F  ?! e
   
7.             maxWeight = maxWeight * 3 + 1;  4 t! a# @1 B, z+ ~5 c0 s/ h/ S
   
8.             minCnt++;  
   , E  Q; J/ p+ q
9.         }  , z$ b# ]) Y8 P2 t3 A# `
   
10.         System.out.println(minCnt);    F2 F) _+ X. ?( S
    
11.     }    l\" o* H\" d\" ^1 }9 M1 \+ G\" p: }8 N6 q
    
12. }8 q) D9 _$ n- e\" |& v+ U% b
    

复制代码

题解
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
此时我们想扩大区间范围就只可以增加砝码
假设增加的砝码重量为 k
7 W$ u% f. c5 e7 Y, h& M) z6 ^因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了

# o. G# b1 ^: J+ e让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
$ N, j3 y' d) n& e+ i/ u5 _
+ k. M" g% J) _另 n + 1 = k - n k = 2n + 1
那么x + 1可以控制的最范围就是[1, 3n + 1]
; `, [5 m- c. p9 H6 D

& r3 D* Z# N  k7 D" G7 }
& ~1 p% k0 `  M