最少砝码问题（用一部分数的和/差表示区间上所有的整数）

问题1, 需要表示[1, N] 的所有重量，最少需要多少砝码？

答案：需要 1，2， 4,  ... , ceiling(logN)，每个砝码代表二进制数的一位，N有ceiling(logN)个二进制位。

问题2， 需要表示[1, N] 的所有重量，手头已有一些砝码，问：怎样添加新的砝码，使得需要添加的砝码数最少？

不变式：curMax为当前可以表示的重量的最大值，也就是[1, curMax] 都可以表示，

算法：从小到大考察已有砝码x，如果x > curMax + 1，则需要把curMax + 1加进去，因为这个值现有的砝码怎么组合都无法表示。然后维护curMax，即加进一个新砝码后，可以表示的新的连续重量最大值。如果x <= curMax + 1, 则curMax 和 x之间没有gap, 只需要维护新的curMax。 循环结束后，如果curMax < N，则需要加进curMax + 1, 更新curMax，如此反复。

vector<int> neededNumber(vector<int> &A, int n) {
	sort(begin(A), end(A));
	int curMax = 0;
	vector<int> ans;
	for (int x : A) {
		while (curMax < n && x > curMax + 1) {
			ans.push_back(curMax + 1);
			curMax += curMax + 1;
		}
		if (curMax == n) return ans;
		curMax += x;
	}
	while (curMax < n) {
		ans.push_back(curMax + 1);
		curMax += curMax + 1;
	}
	return ans;
}

数学归纳：curMax是当前可表示的最大，即[1, curMax]都可以表示，下一砝码的值nextValue用贪心的思想希望它尽可能大，但是要保证[curMax + 1,  nextValue - 1] ]都能被表示，不能有洞，而这个区间的值只能用减法表示 即[nextValue -  curMax,  nextValue - 1],   nextValue - curMax = curMax + 1, nextValue = 2 * curMax + 1。

或者这么理解，每个数都有3种状态1（放左边），0不放，-1（放右边）和题1类似的理解

问题4：同问题3，但是已经有了一些砝码，然后添加新的砝码，怎样最少添加多少个？