- 在线时间
- 480 小时
- 最后登录
- 2026-6-1
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7823 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2934
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1174
- 主题
- 1189
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
问题描述】* [8 r/ Q4 K: H6 l+ S2 h
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。5 d9 C/ n' h# m- `, N) S2 {! \
那么这套砝码最少需要包含多少个砝码?8 V7 Q7 x, F& x) O5 w) V
注意砝码可以放在天平两边。1 v' K. j8 }9 O" c: _
& G- w. @" v, W* `& v) J
【输入格式】
% g$ x2 V9 E& Q: g1 ?输入包含一个正整数 N。9 ]' x6 [( l( L$ b: Z5 j% a" |- {
" M( ]$ R8 ~% I9 a( _+ \【输出格式】. a- |8 E) Z% b6 m2 ?
输出一个整数代表答案。, i8 N) d! R: |+ _
2 k+ \/ i9 h, |- ~& a【样例输入】
0 Z& R0 [% B0 H71 O+ j' y) i2 M; u0 V! D
3 W) J0 p. F' l2 \9 n. v
【样例输出】
8 l5 x2 e4 U: s9 A- e3
* U+ X% f- c$ O, \) v
# k5 s Y9 o7 _0 v) {【样例说明】
( u' _( b( S$ w" n2 c5 I4 [) }3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
+ Z; j: i; o/ Z0 {2 m$ j! Z1 = 1;
$ Z, \2 X) S% Z2 = 6 − 4 (天平一边放 6,另一边放 4);+ z! @6 |$ t$ T0 s# n
3 = 4 − 1;
# u$ Q# e( w, `8 M5 M4 = 4;
8 w1 b) y* X+ c5 = 6 − 1;5 K" N" m, d4 G) ^6 b
6 = 6;
( g3 j; ~5 z. b- r: w% a7 = 1 + 6;
; A$ S! F3 L4 ]( G" }1 l O少于 3 个砝码不可能称出 1 至 7 的所有重量。- import java.util.Scanner; 7 P& Z0 X\" J. t; s; R
- public class Main { ! i4 `; [% x8 m, o
- public static void main(String[] args) {
; W: `& D\" U- j2 R7 ~0 c5 d# V' q - int n = new Scanner(System.in).nextInt(); + Q/ L% `5 |1 D
- int maxWeight = 1, minCnt = 1; 5 R0 }' |4 D) O2 ~) M
- while (maxWeight < n) { ) I' _+ I\" j! Y5 w
- maxWeight = maxWeight * 3 + 1;
M1 }: c2 r1 _% q - minCnt++; $ U5 a! J2 `. l8 a' e9 V9 A, G
- } % E) J+ O- j9 ~0 H' L
- System.out.println(minCnt);
& h0 q4 W% U\" n- y/ `% j2 Q - } * G/ h- o( h, D- n/ S
- }5 l' G' c. f. j- I( x0 E
复制代码 题解
9 |- l, i/ f e0 _" B k& m" Q如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
/ [5 d5 N3 ]/ s# [' k, o& W$ _此时我们想扩大区间范围就只可以增加砝码. K) j ?$ @3 r. x* v4 X! P4 L
假设增加的砝码重量为 k
. H/ ?, @* u s( H# b$ [/ d因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作# n* x. t; u/ ?8 L% P
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
|1 c+ i9 u1 x) `- P* r4 O( q, [: A5 r
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
( V, g& r* o0 |
. L3 k o. T4 c) N. D另 n + 1 = k - n k = 2n + 1
$ a. J' v( A, [! O5 K# D那么x + 1可以控制的最范围就是[1, 3n + 1]
7 U* C- k7 D9 h+ h
6 s6 k7 c: E; ~3 M, G" m* g
# [2 ]8 b9 I* _9 c9 t& [5 r
8 |" k* S& F% C7 b* j* T( M# h |
zan
|