- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
问题描述】- `9 N. h8 D {% r
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。0 `1 o9 A% F8 V6 s n3 Q' H
那么这套砝码最少需要包含多少个砝码?
9 V& I7 n; @8 ~$ t: w+ Z注意砝码可以放在天平两边。- [# L7 ~0 q$ [* _, Q; h% a
; Z6 h4 Z! F( y# h! m( L【输入格式】6 L& x1 u+ d, s, j
输入包含一个正整数 N。/ e6 r ^0 C/ \4 R
2 j( |3 _- v4 X* o2 o" m
【输出格式】
. l9 K. \! h1 ~( s* U- H9 p输出一个整数代表答案。
g; ?; ~. s! U6 A n' l+ D
: d N9 Q" Y7 C【样例输入】
1 q! N4 M- x+ S7 X2 N7
/ V1 f4 n( L0 }0 B1 n2 w; g+ K% U* L
. Y u+ c. ~9 D$ r! R# k, Z【样例输出】
& `! G- ?" \: Y) ~* d" u/ ^6 h3
8 p; H2 \+ ]8 O" e7 N9 Y) R! X4 L! K# |/ c+ N1 P' Y& h1 a4 U
【样例说明】
( [2 {4 x# p4 \$ I- j/ P3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
4 z6 H# h" F1 i' ]- P7 k1 = 1;. H) Q/ v8 q/ J7 `7 q- b! I
2 = 6 − 4 (天平一边放 6,另一边放 4);( I) f! ?$ j! P0 @1 n+ r
3 = 4 − 1;! d; S2 C' Q! `( E
4 = 4;) z8 c+ S) Y( E4 A8 B1 q. P' ^
5 = 6 − 1;. U% W( P( U- X7 U8 P# t; V. |
6 = 6;7 `) f* ?' A# I5 V# u! w. d* Q) r( D1 X+ ~
7 = 1 + 6;7 g' C/ a% L0 r7 {0 i
少于 3 个砝码不可能称出 1 至 7 的所有重量。- import java.util.Scanner;
$ q2 Q. V' _5 T - public class Main {
# ?5 E4 w' g# }) s\" ^; q, ^5 g+ b m - public static void main(String[] args) {
. J0 u8 x% L( q/ Y) u. P+ Q# k - int n = new Scanner(System.in).nextInt();
( M) R6 ~; X; ^/ ] - int maxWeight = 1, minCnt = 1; e7 y, x b Q+ N2 n
- while (maxWeight < n) { 3 K8 _ V$ V) y) F+ U
- maxWeight = maxWeight * 3 + 1;
1 J5 _. p; u) Y - minCnt++;
3 b/ G\" O( O8 |# [ - } # g* F! n- E- |5 ~3 B* H; B
- System.out.println(minCnt); ( J8 z1 J4 S\" W: O0 B8 p
- }
1 W {5 U/ X- ~8 v0 a - }
3 u3 [' C/ ?; [/ \& D! w
复制代码 题解7 O0 q$ H+ h0 H( M) E
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
: P V! z/ h/ s* |: }3 k此时我们想扩大区间范围就只可以增加砝码5 m" U9 |" d5 e6 b( u# o G+ [
假设增加的砝码重量为 k8 p: o$ b, G6 P- [( Y/ T& q
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作% ]# Z9 c2 m, ?, c& T4 n
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了" O+ s8 X" J0 i
c. {$ S1 }& Q, k" _1 j让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围
& X( K( i% z6 H4 S4 [
% E0 v+ H: F) J8 h' M2 s \另 n + 1 = k - n k = 2n + 1
& n3 W) |3 p( U5 R0 F那么x + 1可以控制的最范围就是[1, 3n + 1]
, Q1 z6 t) T+ h. o3 f
: d: j4 U, a3 o7 p+ D9 P. I5 j& D
+ { e6 A: M, x9 l2 Y( B7 `' k( k* P% ~0 W
|
zan
|