A-28的因子

Description

我们都知道28的因子中含有4和7，而某些人偏爱数字4和7； 例如数字：747,4,7747,4,7是兴安黑熊喜欢的数字，而476,5,27476,5,27则不是。 对于给定的数字n，能否找出各个数位上数字和为n的最小的兴安黑熊喜爱的数字。 如果找到则输出这个最小数, 如果找不到，则输出“xinganheixiong”。

Input

多组输入。 每组输入一个整数n(1 ≤ n ≤ 1e6) 代表各个数位上数字的和。

Output

如果兴安黑熊喜欢的话，就输出最小的喜欢数字！ 否则就输出“xinganheixiong”

Analysis

本题的核心就是一个简易的贪心算法，给定一个个数位之和，导出一个由特定元素（4,7）构成的数字的最小值即可

很显然我们可以发现，增加数字的每一位的值远比增加数字的位数来的划算（能够使我们最后导出的数字更小）

遵从这个思路，我们只要按照取尽可能多位的7，将剩下的取为4即可

而输出的时候显然优先输出4，便可以让我们的值为最小

Accepted Code

/*
 * @Author: Gehrychiang
 * @LastEditors: Gehrychiang
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
//又是greedy?说好水体的呢？来自无名大一的愤恨？！！
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        //优先安排7  加数比加位优先
        int max7 = n / 7;
        int dig4 = 0, dig7 = 0;
        for (int i = max7; i >= 0; i--) //i为7的位数
        {
            int rest = n - i * 7;
            if (rest % 4 == 0)
            {
                dig4 = rest / 4;
                dig7 = i;
                break;
            }
        }
        if (dig4 * 4 + dig7 * 7 != n)
        {
            cout << "xinganheixiong" << endl;
        }
        else
        {
            for (int i = 0; i < dig4; i++)
            {
                cout << "4";
            }
            for (int i = 0; i < dig7; i++)
            {
                cout << "7";
            }
            cout << endl;
        }
    }
    return 0;
}