2016级算法第四次上机

975 AlvinZH的1021实验

思路

贪心，简单题。

题目已经说明有且只有一种方法表示所求数，简单列举几项可以发现只由前i个砝码会可以表示[1,∑Wi]的所有数的。先找到最大需要的砝码Wi，问题变成了表示(n-Wi)，可递归，可循环。见看考代码一。

本题亦可联想到三进制，思路清奇。可以参考段柯宇同学的题解。

分析

简单讲讲为什么，贪心在哪里。令W[6]={1,3,9,27,81,243}表示砝码重量，Sum[6] = {1,4,13,40,121,364}表示前i个砝码总和。

可以发现W[i+1]=Sum[i]*2+1(i∈[0,4])，这表明若Sum[i-1]<n≤Sum[i]，能用的最大砝码只能是W[i]。如果最大使用W[i+1]，就算减去所有更小的（即-Sum[i]）结果依然大于W[i]；如果最大使用W[i-1]，就算加上所有更小的（即+Sum[i-2]）变成Sum[i-1]，亦不能表示n。所以判断最大使用的一定是W[i]，而且是输出正的W[i]，废话！

接下来用n-W[i]后，问题就变成了表示（n-Wi)，负数并不是问题，变成正数，输出取负可解决。

参考代码一

//
// Created by AlvinZH on 2017/10/22.
// Copyright (c) AlvinZH. All rights reserved.
//

#include <cstdio>
const int Weight[6] = {1,3,9,27,81,243};
const int Sum[6] = {1,4,13,40,121,364};

int main()
{
int n;
while(~scanf("%d", &n))
    {
int flag = 0;
int i = 0;

while(n > 0)
        {
for (i = 0; i < 6; ++i) {
if(n <= Sum[i])
break;
            }

if(flag == 0)//第一个数
            {
                n -= Weight[i];
                printf("%d", Weight[i]);
            }
if(flag == 1) {
                n -= Weight[i];
                printf("+%d", Weight[i]);
            }
if(flag == -1) {
                n = Weight[i] - n;
                printf("-%d", Weight[i]);
            }

if(n > 0) flag = 1;
else if(n < 0)
            {
                flag = -1;
                n = -n;
            }
        }
        printf("\n");
    }
}