【数学】最少砝码【蓝桥杯】

题目

最少砝码 - 蓝桥云课

---

问题描述

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

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

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

输入格式

输入包含一个正整数 N。

输出格式

输出一个整数代表答案。

样例输入

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$ 的所有重量。

评测用例规模与约定

对于所有评测用例，$1\le N \le 1000000000$。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

解题

方法一：数学 找规律

思路

根据【转载】由数据范围反推算法复杂度以及算法内容，这题 $10^9$ 的数据范围一般需要做到 $O(\sqrt{n})$ 的时间复杂度才能通过，所以这题应该是有通项公式之类的数学方法解决的。

遇事不决先暴力找找规律：

import java.util.*;
import java.io.*;

public class Test {
    static Set<Set<Integer>> st = new HashSet<>();
    static Map<Set<Integer>, Set<Integer>> mp = new HashMap<>();

    static void dfs(int n, int curr, Set<Integer> ws, Set<Integer> fs) {
        if (curr > n) {
            st.add(new TreeSet<>(ws));
            mp.put(ws, fs);
            return;
        }
        for (int i = 1; i <= 30; ++i) {
            if (ws.contains(i)) continue;
            Set<Integer> nw = new HashSet<>();
            Set<Integer> nf = new HashSet<>();
            nw.add(i);
            nf.addAll(fs);
            nf.add(i);
            for (int w : ws) {
                nw.add(i + w);
                nw.add(Math.abs(i - w));
            }
            nw.addAll(ws);
            dfs(n, curr + 1, nw, nf);
        }
    }

    static void test(int n) {
        st.clear();
        dfs(n, 1, new HashSet<>(), new HashSet<>());
        int mx = 0;
        Set<Integer> f = new HashSet<>();
        for (Set<Integer> s : st) {
            List<Integer> lst = new ArrayList(s);
            int sz = lst.size();
            if (lst.get(lst.size() - 1) == sz) {
                if (sz > mx) {
                    mx = sz;
                    f = mp.get(s);
                }
            }
        }
        System.out.println(n + " - " + mx + " - " + f);
    }

    public static void main(String[] args) throws IOException {
        for (int i = 1; i <= 5; ++i) test(i); // 找规律
    }
}

得出了这样的结果：

1 - 1 - [1]
2 - 4 - [1, 3]
3 - 13 - [1, 3, 9]
4 - 40 - [1, 3, 9, 27]

大概能找出规律：每多一个可用的砝码，能称出来的重量上限为上一级的 $3$ 倍加 $1$。

所以写个循环递推找到 能称出任意小于等于 $N$ 的正整数重量 在 最小多少砝码能称出的重量上限之内 即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int x = 0, cnt = 0;
        while (x < n) {
            ++cnt;
            x = x * 3 + 1;
        }
        System.out.println(cnt);
    }
}