- 在线时间
- 468 小时
- 最后登录
- 2025-7-19
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7509 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2833
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1160
- 主题
- 1175
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
问题描述】3 s5 A' Z+ a/ Y% Y1 i. V
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
' y" A. Z" s# a' {9 E( }5 o那么这套砝码最少需要包含多少个砝码?
1 D. _8 c" z' |3 G& _注意砝码可以放在天平两边。5 e9 `/ {, K$ v1 A! U3 N; S1 M
( Z4 k/ N p+ }% k4 {: {, d; N0 m
【输入格式】
6 ]! s0 i" ^& R; [% C* Y; f输入包含一个正整数 N。
* V* r# d! ]3 Y( M; v4 i0 {6 |8 w0 J" c& o! u+ p0 [1 S4 M% _
【输出格式】
' `/ N) A w. u- e6 E输出一个整数代表答案。, n/ r+ R! @, j* d; j7 N
) j! e/ b' I: _7 Z6 o【样例输入】
( C6 h6 e, {$ M7$ j0 A3 z1 w: c7 `: O" m
. z v2 h# ]) N【样例输出】
) ^) }: J* A6 g3 [: i, N6 |$ v5 Q. |, ?$ `
8 y8 ?1 ]% A! W+ m _+ s
【样例说明】, S, |' d: R: i# b8 G7 P
3 个砝码重量是 1、4、6,可以称出 1 至 7 的所有重量。
$ f) M% ]. [7 Q' ]# u1 = 1;
1 f3 n- T/ K" x& e2 = 6 − 4 (天平一边放 6,另一边放 4);( o. i: R( [- x4 ?6 h
3 = 4 − 1;4 ]8 k' p- S# k5 n
4 = 4;
2 e2 n/ u1 ?+ S- p' @; t) O2 r, J4 e5 = 6 − 1;
! `' x7 e t0 o6 = 6;
. a+ ?" L0 u- d1 f+ t# t7 = 1 + 6;+ y$ B5 q# N i* _5 y
少于 3 个砝码不可能称出 1 至 7 的所有重量。- import java.util.Scanner;
f ?, k5 `, u+ o\" L. q7 D - public class Main { % G9 m, N1 Z# Y. q\" o7 j& b
- public static void main(String[] args) {
& J* [$ L! @6 C0 L; Y' U - int n = new Scanner(System.in).nextInt(); ) J$ y! e# E n8 w; B- \+ O# D, A) v
- int maxWeight = 1, minCnt = 1;
; b7 v8 t/ I/ J ]4 u7 f - while (maxWeight < n) { + n) R: U% C6 l, l V6 y! ^
- maxWeight = maxWeight * 3 + 1; ) b% y/ Q W9 h6 A
- minCnt++;
* v1 E( n- O: i0 I9 G! F - } \" D j* v8 m+ [% s6 m+ J/ O
- System.out.println(minCnt); + G0 Z) Y2 ~& l/ `
- }
* a. \3 o! [# R- d9 H - }
6 K( L2 o- K P1 q
复制代码 题解8 w1 T+ Y+ o9 d+ j7 U; i, R
如果我们可以控制的区间范围 是 [1, n] 最少砝码为x个
. m* W6 ^0 x2 E" V0 u此时我们想扩大区间范围就只可以增加砝码3 S. w; y& D; [
假设增加的砝码重量为 k( A( [+ y7 `5 Z
因为我们可以控制 [1, n] 的重量, 而且因为可以把砝码放在左右两把, 想当于我们可以进行加减操作: o3 J) I/ H& m K) w w
所以新增砝码后, 我们又可以控制[k - n, k + n] 的区间范围了0 Q0 _ L) i6 O" Y& s4 p: ]* i
! k& y& m g5 x8 @& b让这个新增的控制范围 与 我们原来的可以控制的范围相邻, 就得到了最大的可控范围& e% c3 |3 H# k4 ]$ v1 X, {
$ O) m& ~/ V; @. p+ a# W
另 n + 1 = k - n k = 2n + 1
3 M( ^& m. q8 c9 L/ }3 }8 P那么x + 1可以控制的最范围就是[1, 3n + 1]
_9 b! Z! e% r3 O/ k" [$ l
3 D8 w6 W8 u- b& t+ N
) w& D4 q$ b7 t8 y
* H+ N3 M( B: T: c |
zan
|