2021省赛 最少砝码 java

找规律+贪心

如果称重1，需要一个砝码其重量为1；我们要加的砝码的重量，经过组合要能够表示较大的数，比如第一个砝码重量为1，该表示重量为2的，那么下一个加2还是3？
2.1 如果加2，则能表示：1+2,2-1,1，2，最多只能表示到1,2,3；
2.2 如果加3，能表示：1+3,3-1,1，3，最大可以表示到4，且1到4都可以表示此时砝码的个数为2个（重量为1和重量为3）；可以表示的范围为[1,4];我们又该找能表示重量为5的，我们利用贪心的思想（要加的砝码的重量，经过组合要能够表示较大的数）；所以我们要找谁减去现有的最大重量可以表示5 ；那么我们可以知道下一个加砝码重量为9；9-3-1==5；如果加重量为9的这个，那么现有的三个砝码可以表示的最大重量为：1+3+9=13；我们可以测试下是否满足[5,13]，这些范围内的数；经过运算可以发现，可以；规律：

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans = 1;// 初始只有一个重量为1的砝码
		int max = 1;// 所有砝码的组合最大可以称的重量
		while (max < n) {
			ans++;// 多加一个砝码，其重量为前一个砝码的3倍
			max = (3 * max + 1);// 加一个后，可称的最大重量为上一个的3倍+1
		}
		System.out.println(ans);
	}
}