牛客寒假算法基础集训营2 处女座的砝码 （思维）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了牛客寒假算法基础集训营2 处女座的砝码 （思维），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1193字，纯文字阅读大概需要2分钟。

内容图文

处女座的砝码 

链接：https://ac.nowcoder.com/acm/contest/327/C

题目描述

处女座热爱做物理实验，为了实验，处女座必须要精确的知道物品的质量。处女座准备自己设计一套砝码，每一个砝码都是正整数，这套砝码必须能够精确测量出n以内所有正整数的质量，处女座想要知道至少需要多少个砝码。你可以在天平的任意一边放置砝码。

输入描述:

一行，一个正整数n  1<=n<=10^1000

输出描述:

一个整数，表示最少的砝码数。

示例1

输入

20

输出

4

说明

你可以选择1，2，6，11
1=1
2=2
3=1+2
4=6-2
5=6-1
6=6
7=6+1
8=6+2
9=6+2+1
10=11-1
11=11
12=11+1
13=11+2
14=11+2+1
15=11+6-2
16=11+6-1
17=11+6
18=11+6+1
19=11+6+2
20=11+6+2+1

题意：每个砝码可以放左边，不放和右边，很容易联想到三进制，所以按照3 进制排列即可，选择砝码如下：1,3,9,27,… 

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3   
 4 public class Main {
 5     public static void main(String[] args) {
 6         Scanner cin = new Scanner(System.in);
 7         BigInteger n = cin.nextBigInteger();
 8         BigInteger now = BigInteger.valueOf(1);
 9         int cnt = 1;
10         while(n.compareTo(now)>0) {
11             cnt ++;
12             now = now.multiply(BigInteger.valueOf(3));
13             now = now.add(BigInteger.valueOf(1));
14         }
15         System.out.println(cnt);
16     }
17 }

 

内容总结

以上是互联网集市为您收集整理的牛客寒假算法基础集训营2 处女座的砝码 （思维）全部内容，希望文章能够帮你解决牛客寒假算法基础集训营2 处女座的砝码 （思维）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---