题解 | #小红的375#

首先观察 的特点，发现 ，因此答案需要同时满足 的倍数和 的倍数的特征。 的倍数需要满足各数位相加之和是 的倍数； 的倍数没有显然的结论，但发现 ，类比 的倍数结尾只能是 或 的结论，可以联想到所有 的倍数的后三位只有可能是 中的一个。 由此得到做法，首先判断输入数据有没有可能组成 的倍数，再枚举这八种结尾，依次判断能否组成合法答案即可。由于题目规定输出不能有前导零，我们要判断是否还剩余除 之外的数位用于组成答案，需要注意的是长度为 时不需要多余数位，特判即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;



string check[10] = {"000", "125", "250", "375", "500", "625", "750", "875"};

void solve(){
    string s;
    cin >> s;
    ll sum = 0;
    map<int, int> mp;
    for (int i = 0; i < s.size(); i++) {
        int num = s[i] - '0';
        mp[num]++;
        sum += num;
    }
    if (sum % 3) {cout << -1; return;}

    auto work = [&](string str) -> int {
        map<int, int> mpp = mp;
        for (int i = 0; i < 3; i++) {
            if (mpp[str[i] - '0']) mpp[str[i] - '0']--;
            else return 0;
        }
        bool flag = false;
        if (s.size() == 3) flag = true;//特判长度为3
        for (int i = 1; i <= 9; i++) if (mpp[i]) flag = true;//判断是否有除0外的数位
        if (flag) {
            for (int i = 9; i >= 0; i--) {//倒序输出，保证无前导0
                for (int j = 1; j <= mpp[i]; j++) cout << i;
            }
            cout << str;
            return 1;
        }
        else return 0;
    };

    for (int i = 0; i < 8; i++) {
        if (work(check[i])) return;
    }
    cout << -1;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _T = 1;
    // cin >> _T;
    while (_T--){ 
        solve();
    }
    return 0;
}