UVA 10560 - Minimum Weight

题意：有一个天枰，给定n。要求出能称出1 - n重量所需最少的砝码，然后给k个数字，分别表示出怎么去称这k个数字。

思路：首先先求出最少砝码，1肯定是须要的。然后1能够组成1，然后要1个3。就能够组成2，3，4观察后发现，事实上每次加入砝码，就加入当前砝码总质量和 * 2 + 1.

证明：当前砝码能组成[1, sum]那么在多一个砝码，假设有2 sum + 1, 那么[sum + 1, 2 sum + 1]的情况都能够组成，这样是最优的使得砝码最少。

然后剩下就是去表示重量怎样组成了，事实上就是加加减减，推断当前重量是否在sum[i - 1] 和 sum[i]之间。假设是的话，就是能够用一个need[i]这个砝码，至于加减。就要看之前的情况了，我是用了一个flag来标记。

代码：

#include 
     
      #include 
      
       const int N = 105;const char fh[5] = "+-";unsigned long long n, need[N], sum[N], w;int k, nn = 0;void solve(int i, unsigned long long w) {    int flag = 1;    while (w) {	for (;i >= 1; i--) {	    if (w <= sum[i] && w > sum[i - 1]) {		printf("%llu", need[i]);		if (w > need[i]) {		    w -= need[i];		    printf("%c", fh[(!flag)]);		}		else if (w < need[i]) {		    w = need[i] - w;		    printf("%c", fh[flag]);		    flag = (!flag);		}		else w = 0;		i--;		break;	    }	}    }    printf("\n");}int main() {    unsigned long long Max = (1ULL<<63), now = 0;    while (now < Max) {	nn++;	now = sum[nn - 1] * 2 + 1;	sum[nn] = sum[nn - 1] + now;	need[nn] = now;    }    need[++nn] = (1ULL<<64) - 1;    sum[nn] = need[nn];    while (~scanf("%llu%d", &n, &k) && n || k) {	int i = 1;	for (; i <= nn; i++) {	    if (n <= sum[i]) break;	}	printf("%d", i);	for (int j = 1; j <= i; j++)	    printf(" %llu", need[j]);	printf("\n");	while (k--) {	    scanf("%llu", &w);	    solve(i, w);	}    }    return 0;    }