- 在线时间
- 326 小时
- 最后登录
- 2024-5-10
- 注册时间
- 2023-7-11
- 听众数
- 1
- 收听数
- 0
- 能力
- 0 分
- 体力
- 5237 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 1970
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 798
- 主题
- 796
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
|
问题描述】
9 j/ o2 P! Z5 l6 K; G1 m C" k你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
9 d8 P, Z# _8 b. ^( k. \% Y' I那么这套砝码最少需要包含多少个砝码?
! O' }) P* Z( x7 S: x注意砝码可以放在天平两边。( F+ r0 |0 B' X$ y9 N* r
! W. H+ b& J P) Q1 b
【输入格式】8 R9 ?, S9 h. F
输入包含一个正整数 N。
! L3 Y U7 V5 J( R; ~: {* q4 p' F f1 [4 P! S/ Q: O5 H9 |* ]
【输出格式】
- U+ V$ ^9 r9 P4 r8 W" }; R2 d. i, P: J输出一个整数代表答案。: o8 M3 y4 a3 l0 _9 M2 I5 u4 j
9 A" }( ?. Y6 |! p
【样例输入】6 a4 G6 h' S' a1 I+ m( }
7
1 j, D' L/ F, _5 }3 ?; f1 j
/ I3 u/ L3 E$ f; I) ]【样例输出】
6 f9 _3 z/ J" W& ?$ Q5 u3. e0 R7 W2 p* m3 U3 e, t* m
% g/ @( n( Q' Q7 z5 \, v4 V
【样例说明】
3 r9 u5 N& k& B2 e4 S$ E3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。. j- g" C6 F% D8 S1 a3 h; E. }" o) O
1 = 1;
2 x7 d+ j+ {( { T0 A. r$ W2 = 6 − 4 (天平一边放 6,另一边放 4);- B7 M6 l: h: h% i! S# L) N4 [
3 = 4 − 1;
& \. ~6 f/ l/ y& v4 = 4;
/ r, i' S9 B r8 Z9 F6 {( z8 g& A# I5 = 6 − 1;
: w* F* d* ^: X1 k/ L5 N* A* t6 = 6; z( h# {$ E5 X3 h; J
7 = 1 + 6; T# ^4 i# B0 k
少于 3 个砝码不可能称出 1 至 7 的所有重量。- import java.util.Scanner; : H1 ~3 |) l\" ^- d% _/ y& H
- public class Main {
6 B; R7 g& U. r1 n8 e8 k4 Q p0 f - public static void main(String[] args) { # m0 y$ i/ @$ _- w& V4 e
- int n = new Scanner(System.in).nextInt();
: E! V% ?1 o. ? - int maxWeight = 1, minCnt = 1;
/ [# h& y4 F% H. g. [ - while (maxWeight < n) { 1 u' @. I7 E+ F% L' v
- maxWeight = maxWeight * 3 + 1; 7 P& D; C& H, z) [9 m\" W p! R
- minCnt++;
) u2 h3 ^( k# p: q& D& n - }
% i) R: E0 b0 n% O+ h$ P* c - System.out.println(minCnt); 8 ~$ p# p# x% j5 v
- }
# u% [9 {$ n! _& k - }
0 P. z f- P* P$ k0 x
复制代码 题解
: E& Z: x( T8 T0 l$ k( N% x0 Q如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
+ O% M$ N1 B- h此时我们想扩大区间范围就只可以增加砝码: }$ l! c: Z$ O p% w' O
假设增加的砝码重量为 k' ]# \7 q" T$ t! U3 s
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作 p4 E3 K* |2 Z' j
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了
" h5 ~" z. u. Z+ N2 W- E6 ]) z W" G S% L u$ G) f
让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围- f: s! F! m+ [) H1 N. E8 F5 x) E
$ `6 N5 ^/ W6 W. F另 n + 1 = k - n k = 2n + 1: P6 U$ z1 h, R1 o: B, ^2 L# q5 ~
那么x + 1可以控制的最范围就是[1, 3n + 1]
) f6 E$ Y( |" _) B; l7 Y; [. Q* C. j! [# ]; ~4 n+ U" B& z+ n
4 C9 i8 G, l/ q& K! Y0 H
9 k' ]2 `9 @% F O8 B4 u
|
zan
|