題目鏈接
題意:有一個天枰,給定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; }