最少砝码

题目

3424. 最少砝码 - AcWing题库

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 $N$ 的正整数重量。

那么这套砝码最少需要包含多少个砝码？

注意砝码可以放在天平两边。

输入格式

输入包含一个正整数 $N$。

输出格式

输出一个整数代表答案。

数据范围

对于所有评测用例，$1≤N≤10^9$。

输入样例：

7

输出样例：

3

样例解释

$3$ 个砝码重量是 $1、4、6$，可以称出 $1$ 至 $7$ 的所有重量。

1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。

思路

假设$n$个砝码能够表示的范围为$[0,k]$

如果第$n+1$个砝码的重量为$2k+1$

那么$k+1$的重量可以表示为$(2k+1) - k$

$k+2=(2k+1)-(k-1)$

…….

$3k=(2k+1)+(k-1)$

$3k+1=(2k+1)+k$

假设$f[i]$为共$i$个砝码能够表示的范围$k$

所以$f[i+1]=3*f[i]+1$

$f[1]=3^0=\frac{3^1-1}{2}$

$f[2]=3^1+3^0=\frac{3^2-1}{2}$

$f[3]=3^2+3^1+3^0=\frac{3^3-1}{2}$

…

$f[n]=\frac{3^n-1}{2}$

假设输入的值为$m$

那么$f[n]>=m$

即$\frac{3^n-1}{2}>=m$

化简得$3^n>=2m+1$

$n>=log_3(2m+1)$

得出：$n=\lceil log_3(2m+1) \rceil$

代码

import java.util.*;

public class Main
{
    static int n, cnt = 0;
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();

        inScanner.close();
        System.out.println((int)Math.ceil(Math.log(2*n+1)/Math.log(3)));
    }
}
/*
3 3
0 3
1 2
0 2
*/