在线时间 480 小时 最后登录 2026-6-1 注册时间 2023-7-11 听众数 4 收听数 0 能力 0 分 体力 7823 点 威望 0 点 阅读权限 255 积分 2934 相册 0 日志 0 记录 0 帖子 1174 主题 1189 精华 0 分享 0 好友 1
该用户从未签到
问题描述】3 `4 `& V& a" M
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。' w/ ]2 b+ n) K
那么这套砝码最少需要包含多少个砝码?
/ Y* \+ {4 q4 { 注意砝码可以放在天平两边。( x! B0 U; b* f' u9 B) F
4 f* m7 E- s% c0 \ 【输入格式】" d L" ?; o; z
输入包含一个正整数 N。+ f7 \+ T, K- p" o
[0 }" j; m; N8 ^ 【输出格式】
?+ S( G. M* J# y N! X 输出一个整数代表答案。8 d+ |1 l. F3 d% p4 d. Z
! w+ m& K8 {) `7 r% u 【样例输入】
+ A( V6 j" g. S" t; L 7
5 K- d, S3 K% x' l' H; N
- _7 }* \' h3 n2 e6 [% N x 【样例输出】$ K' m7 c9 n) W5 e; v' o7 K& o
3
* u/ @9 w2 L9 N' K; ?
( u/ b) c+ o3 C7 d+ t+ b B 【样例说明】
3 I1 J; w1 x T/ T' D0 R% u8 ] 3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
) U' [3 x9 x* r& y8 t* E 1 = 1;0 k- V/ f: [- c+ T0 |1 @* \
2 = 6 − 4 (天平一边放 6,另一边放 4);. D4 w8 o5 Q' x g5 W( k$ r: H; J
3 = 4 − 1;
% D4 X" _. C0 G 4 = 4;2 d- ]. c0 Z; ?- l1 ~! m0 N
5 = 6 − 1;
* X- }) b- v+ `0 I 6 = 6;
6 Z0 c, z1 X" f! [% u1 x2 L7 n 7 = 1 + 6;6 ~' D* Y. u/ p# n7 N
少于 3 个砝码不可能称出 1 至 7 的所有重量。import java.util.Scanner; 9 t$ J0 [' y+ {% X
public class Main {
0 c& R! n6 p. L+ Q7 X3 }1 ]: F\" O public static void main(String[] args) {
\" @2 x3 L+ p) J$ o1 A int n = new Scanner(System.in).nextInt();
+ X; j2 i5 c$ _1 T int maxWeight = 1, minCnt = 1; , u) c\" e# [4 ^' g% t* b3 `8 F
while (maxWeight < n) {
+ t. f( m9 g6 `7 U+ Y4 G' L maxWeight = maxWeight * 3 + 1; , z- {' Q0 v8 V, u
minCnt++; 5 {5 Y! i, k\" x! _
} 0 E% n: l7 D; V% u
System.out.println(minCnt); 3 Y: ^( e8 P\" v& g9 l7 G1 B. [
} 2 U! U6 b) B0 f( ]2 h0 x# s\" E, D
}
m A( d) g0 U9 z 复制代码 题解* z. u; D# K8 ~4 p
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
; }* G1 S. U% l0 Q4 R/ o- m3 P 此时我们想扩大区间范围就只可以增加砝码) l. ^1 f) f. J3 T$ B
假设增加的砝码重量为 k
" y7 V7 n: n( J7 ~3 I 因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作
# ?$ W9 D* [' ?$ M. E3 q# q 所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
+ _- I4 B p( A$ e
* ~4 k: |2 b/ X. ~& j; U 让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围8 k I6 U* [$ k1 U
2 t2 d. @6 @* `' E; X9 ]+ e( k 另 n + 1 = k - n k = 2n + 1
! \% `- z8 m; c, f 那么x + 1可以控制的最范围就是[1, 3n + 1]9 t W% ^1 Z) Z: Z$ ^0 o( k8 O
. p$ O! i, y, z9 Z: K V" _" h% e6 r7 y$ z4 w
" o3 A4 w t, h1 d0 s' {
zan