- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
问题描述】
7 a+ ?# i) a9 v1 I你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。; P- D# q0 w7 N o
那么这套砝码最少需要包含多少个砝码?- u8 b& V: q. a3 b& l/ p
注意砝码可以放在天平两边。- {2 D8 i& t8 T! \
3 k9 e5 j5 \+ t/ O【输入格式】
# m1 l5 B Q e0 i) x- Z输入包含一个正整数 N。
+ y- x P+ R) l Y* x0 w5 P/ E' X5 u* b0 \" m/ k/ a- I/ f
【输出格式】! C! ~4 ^0 i3 I
输出一个整数代表答案。4 r( f8 A: _' v, r8 P& @* C& {% T
: ?3 Q0 i/ j+ L【样例输入】6 r- w# x' {- B8 `
7
. ^4 P: b! ^% L; Q! m; U+ V8 W
$ N% i: E7 @! R1 q$ c. l【样例输出】% J* I; |) z q5 X% n) X
3
/ M' E$ v( j9 B) B; ^) L! A6 `
4 @4 c3 g2 B7 ~0 L【样例说明】) I' _4 C' \8 O3 T) w+ ?, f
3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
9 K& T, ?5 `; J) E% }1 = 1;
8 ~( U, V& }3 }3 m( N6 A2 = 6 − 4 (天平一边放 6,另一边放 4);
2 `8 L0 h6 J7 }* A: @/ x1 |- m3 = 4 − 1;2 [: t/ d) b- x* `9 a7 E
4 = 4;
3 u/ ]% J5 f; m5 = 6 − 1;, F! ?" w0 P( ?1 u0 [8 u
6 = 6;/ F v6 u( d% e
7 = 1 + 6;$ t2 Q& F7 C1 u. I
少于 3 个砝码不可能称出 1 至 7 的所有重量。- import java.util.Scanner;
) _& t5 U% N8 s! Y, K( S - public class Main {
5 b5 c) P6 t: `1 m5 f - public static void main(String[] args) {
% ~. z, Y7 R; q& X- `\" l - int n = new Scanner(System.in).nextInt();
0 x$ r& R3 a) t \1 Z% \7 T - int maxWeight = 1, minCnt = 1; : O& }2 C9 ~* \: Q
- while (maxWeight < n) {
* E! f5 w\" L9 ^/ o9 Y Z - maxWeight = maxWeight * 3 + 1; . D9 d$ V# n! \7 t8 B7 H\" Q
- minCnt++;
# T( Z: I# ]0 A7 L8 J( A - } ! l. u4 ^1 ]# z+ h0 C6 l+ d
- System.out.println(minCnt);
* J; M& Q: r+ } X2 r& l - } 9 O {/ J& ?; m# G/ D/ K& [+ e5 e
- }
7 c* }' A+ U+ @
复制代码 题解5 H% T0 u6 \" ]5 O j
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
$ V/ w7 h4 r- K" \- a' Y8 A9 V此时我们想扩大区间范围就只可以增加砝码2 f: E6 Y/ q9 C# g; A# @
假设增加的砝码重量为 k, y7 F" L- t6 p e+ s1 V; u' Z5 l& C
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
' j. ], h& l+ i; x/ |所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
4 r2 Q S/ K) \- Y
. H9 r6 L3 t& J让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
% \' Z4 _( f$ a" |! F
2 J, T! h: _) H另 n + 1 = k - n k = 2n + 1
% z4 ^3 t; y$ m, u1 Z那么x + 1可以控制的最范围就是[1, 3n + 1]3 e% h" u8 K( W7 k' Y- q7 W9 ?
( Y4 u2 h- N$ F2 b
8 W$ ^8 j) y; P4 u& m& C, M* y9 ]1 T3 X6 c; m6 o! ]2 N
|
zan
|