UVA 10560 Minimum Weight 三進制砝碼最優表示與構造

證明：當前能表示 [1, S]，加入 2S+1 可擴展到 [1, 3S+1]，砝碼數最少。

表示構造算法

目標重量 W，從最大砝碼向下貪心：

• 若 W > 當前砝碼：放右盤，W -= 砝碼，標記 '+'
• 若 W < 當前砝碼：放左盤，W = 砝碼 - W，標記 '-'，翻轉後續符號邏輯
• 若相等：放右盤，結束

代碼實現

ull need[105], sum[105];
void init() {
    need[1] = 1; sum[1] = 1;
    for (int i = 2; i <= 100; i++) {
        need[i] = sum[i-1]*2 + 1;
        sum[i] = sum[i-1] + need[i];
    }
}
void solve(int maxIdx, ull w) {
    int flag = 1; // 1 表示正常，0 表示符號翻轉
    while (w) {
        for (int i = maxIdx; i >= 1; i--) {
            if (w <= sum[i] && w > sum[i-1]) {
                printf("%llu", need[i]);
                if (w > need[i]) { w -= need[i]; putchar(flag?'+':'-'); }
                else if (w < need[i]) { w = need[i] - w; putchar(flag?'-':'+'); flag ^= 1; }
                else w = 0;
                break;
            }
        }
    }
    puts("");
}

關鍵細節

• 用 unsigned long long 防溢出（need[100] ≈ 3^100）
• flag 變量追蹤符號翻轉狀態
• 輸出格式：砝碼值緊跟 + 或 -，最後換行