侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-01-17 / 0 评论 / 0 点赞 / 25 阅读 / 811 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-18,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

最少砝码 - 蓝桥云课


问题描述

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

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

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

输入格式

输入包含一个正整数 N。

输出格式

输出一个整数代表答案。

样例输入

7

样例输出

3

样例说明

33 个砝码重量是 1461、4、6,可以称出 1177 的所有重量。

1=11=1

2=642=6−4(天平一边放 66,另一边放 44);

3=413=4−1

4=44=4

5=615=6−1

6=66=6

7=1+67=1+6

少于 33 个砝码不可能称出 1177 的所有重量。

评测用例规模与约定

对于所有评测用例,1N10000000001\le N \le 1000000000

运行限制

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

解题

方法一:数学 找规律

思路

根据【转载】由数据范围反推算法复杂度以及算法内容,这题 10910^9 的数据范围一般需要做到 O(n)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]

大概能找出规律:每多一个可用的砝码,能称出来的重量上限为上一级的 33 倍加 11

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

代码

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);
    }
}

0

评论区