1284: Gold Medal
题目
有N个砝码，重量为：3i-1（1<=i<=N），有一块重量为 W 的金牌。现在将金牌放在天平的左边。你需要将砝码放在左边或右边使得天平平衡，如果不能平衡输出"No way!"，N个砝码不需要全部用完。更多内容点击标题。
参考
分析
说实话，我也没想到这种做法，看的参考博客才明白的。（感觉他有部分代码处理的不是很好，可能是语言不同的关系吧。）
没见过这类题的话，说实话不容易一下子想到居然和进制居然有一点点关系。
不得不说砝码的重量很灵性。我们可以尝试在这里入手。首先将金牌的重量 W 转成三进制的，由于长度较大所以直接用数组保存比较好（我用的byte[]）。下面举个例子：
输入：
4 16
输出：
LEFT:3 9
RIGHT:1 27
步骤：
通俗讲：
将金牌分成9,6,1三部分（提醒：金牌是固定放在左边的。16的三进制为121），然后发现砝码中有1，
于是就把1放在右边和左边的1平衡，然后继续，发现没有重量为6的砝码，但是你发现有重量为3和9的砝码，
于是就把3放左边，9放在右边，这样就与左边的6平衡了。继续，左边还有9，可是你还剩一个砝码（27），
根本不能平衡。于是你尝试将上一步中的9放在左边，此时左边有3，9和金牌的16一共是28，右边只有1，
但是还剩一个砝码（27），放在右边刚刚好。
代码流程：
16转成三进制为：121 // 左边高位，右边低位
第0位是'1'，所以3^0=1放在右边
第1位是'2'，权重是3^1=3，所以2*3=6，因为6不是3的幂，可是6=9-3，9和3都是3的幂，于是将3放
在左边，然后将121变成221
第2位是'2'，权重是3^2=9，所以2*9=18，因为18不是3的幂，可是18=27-9,27和9都是3的幂，于是
将9放在左边，然后将221变成1221
第4位是'1'，权重是3^3=27，所以1*27=27，是3的幂，于是将27放在右边。
代码
/**
* time 741ms
* @author PengHao
* @version A1.0
* @date 2019-04-29 下午5:39:25
* Environment: Windows 10
* IDE Version: Eclipse 2019-3
* JDK Version: JDK1.8.0_112
*/
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
/**
* @Field <code>wTernary</code> W的三进制字节数组，下标从0开始
*/
private byte[] wTernary;
/**
* @Field <code>leftArr</code> 左边的砝码情况
*/
private byte[] leftArr;
/**
* @Field <code>rightArr</code> 右边的砝码情况
*/
private byte[] rightArr;
/**
* @Field <code>tab</code> 3的n次幂(0<=n<=29)，下标从0开始
*/
private long[] tab;
/**
* @Field <code>ARR_LENGTH</code> 数组长度30
*/
private int ARR_LENGTH = 30;
public Main() {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
initTab(); // 初始化
int N, W;
while (sc.hasNext()) {
N = sc.nextInt();
W = sc.nextInt();
wTernary = toTernary(W); // 转换成三进制
weighing(wTernary); // 称重
if (numOfWeights() <= N) {
output(); // 输出
} else {
System.out.println("No way!");
}
System.out.println(); // 每组数据末尾空一行
}
sc.close();
}
/**
* Initialize <code>tab[]</code>
*
* @see #tab
*/
private void initTab() {
tab = new long[ARR_LENGTH];
tab[0] = 1;
for (int i = 1; i < ARR_LENGTH; i++) {
tab[i] = tab[i - 1] * 3;
}
}
/**
* Converts an integer to a ternary byte array
*
* @param x 整数
* @return x的三进制字节数组
*/
private byte[] toTernary(int x) {
byte[] y = new byte[ARR_LENGTH];
for (byte i = 0; i < ARR_LENGTH && x > 0; i++) {
y[i] = (byte) (x % 3);
x /= 3;
}
return y;
}
/**
* @param x 需要称的重量
* @see #leftArr
* @see #rightArr
*/
private void weighing(byte[] x) {
leftArr = new byte[ARR_LENGTH]; // 保存左边砝码
rightArr = new byte[ARR_LENGTH]; // 保存右边砝码
for (int i = 0; i < ARR_LENGTH; i++) {
switch (x[i]) {
case 1:
rightArr[i] = 1; // 砝码3^i放到右边
break;
case 2:
leftArr[i] = 1; // 砝码3^i放到左边
x[i + 1]++; /// 要研究一下自增和赋值谁快
break;
case 3:
x[i + 1]++;
break;
default:
}
}
}
/**
* @return 砝码个数
*/
private int numOfWeights() {
int num; // 砝码个数
for (num = ARR_LENGTH - 1; num >= 0; num--) {
if (0 != leftArr[num] || 0 != rightArr[num]) {
num++;
break;
}
}
return num;
}
/**
* Output
*/
private void output() {
outputArr("LEFT:", leftArr);
outputArr("RIGHT:", rightArr);
}
/**
* @param LR 左右？
* @param arr 需要输出的砝码
*/
private void outputArr(String LR, byte[] arr) {
boolean first = true; // 是不是第一个砝码
System.out.print(LR);
for (int i = 0; i < ARR_LENGTH; i++) {
if (1 == arr[i]) {
if (first) {
first = false;
} else {
System.out.print(" "); // 不是这一边的第一个砝码，要输出空格
}
System.out.print(tab[i]); // 输出砝码重量
}
}
System.out.println();
}
public static void main(String[] args) {
new Main();
}
}
写在最后：
- 如需转载，请于首页至少注明链接形式的wowpH的博客这几个字；
- 代码原创，如需公开引用，不能删除首行注释（作者，版本号，时间等信息）。
- 如果有疑问欢迎评论留言，尽量解答。