小红的375 - 题解

题目描述

小红拿到了一个正整数，她希望你能重排这个正整数的数位，使得它能被375整除。你能帮帮她吗？

输入： 一个正整数，大小不超过10^300000

输出： 如果无法完成重排，请输出-1。否则输出任意合法解即可。请注意务必保证输出的数不含前导零，且是375的倍数。输出数的长度、包含的每个数字的出现次数必须和输入的数相等。

算法思路

核心观察

要解决这个问题，我们需要理解375的数学性质：

375 = 3 × 125 = 3 × 5³
一个数能被375整除，当且仅当它同时能被3和125整除

关键性质

被3整除的条件： 各位数字之和能被3整除
被125整除的条件： 最后三位数字组成的数能被125整除

125的倍数规律

125的倍数在最后三位有以下模式：

000, 125, 250, 375, 500, 625, 750, 875

算法步骤

1. 预处理

统计每个数字的出现次数
计算所有数字之和，检查是否能被3整除

2. 枚举最后三位

对于每个可能的125倍数后缀（000, 125, 250, 375, 500, 625, 750, 875）：

检查是否能用剩余数字组成这个后缀

3. 构造答案

将剩余数字按降序排列（这样保证没有前导零）
在末尾添加选定的三位后缀

代码实现

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

// 125的倍数在最后三位可能的形式
string check[8] = {"500", "000", "750", "250", "125", "375", "625", "875"};

int tong[10]; // 统计每个数字的出现次数

int main(){
    string s;
    cin >> s;
    
    int sum = 0;
    // 统计数字出现次数并计算数字和
    for(int i = 0; i < s.length(); i++){
        tong[s[i] - '0']++;
        sum += s[i] - '0';
    }
    
    // 检查数字和是否能被3整除
    if(sum % 3 != 0){
        cout << -1;
        return 0;
    }
    
    // 尝试每种可能的后缀
    for(int i = 0; i < 8; i++){
        // 临时减去后缀所需的数字
        for(int j = 0; j < 3; j++){
            tong[check[i][j] - '0']--;
        }
        
        // 检查是否所有数字都够用
        bool valid = true;
        for(int j = 0; j <= 9; j++){
            if(tong[j] < 0){
                valid = false;
                break;
            }
        }
        
        if(valid){
            // 输出剩余数字（降序排列，避免前导零）
            for(int j = 9; j >= 0; j--){
                while(tong[j] > 0){
                    cout << j;
                    tong[j]--;
                }
            }
            // 输出后缀
            cout << check[i];
            return 0;
        }
        
        // 恢复数字计数
        for(int j = 0; j < 3; j++){
            tong[check[i][j] - '0']++;
        }
    }
    
    cout << -1;
    return 0;
}

算法分析

时间复杂度

O(n + 8 × 10) = O(n)，其中n是输入数字的长度
对于每个可能的后缀，只需要常数时间检查

空间复杂度

O(n)，只使用了固定大小的数组，其中n是输入数字的长度

算法优化思考

为什么选择这个后缀顺序？

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

"带0"的优先： 如果存在足够的0，使用"000"、"750"等后缀可以最大化末尾0的数量

关键：规避前导零问题

这个顺序设计的一个重要目的是规避前导零问题。让我们看一个具体例子：

例子：输入 "3075"

如果先尝试"375"后缀，可能会错误地输出"0375"（有前导零）
但如果先尝试"750"后缀，会正确输出"3750"

因此，优先判断以0结尾的后缀（如"000", "750", "250"等）可以避免前导零问题，因为这些后缀会多"消耗"掉一些0，减少前面出现前导零的可能性。

为什么从大到小输出？

for(int j = 9; j >= 0; j--){
    while(tong[j] > 0){
        cout << j;
        tong[j]--;
    }
}

避免前导零： 从大数字开始输出，自然避免前导零

常见错误

1. 忘记检查数字和能否被3整除

// 错误：直接尝试后缀
// 正确：先检查数字和
if(sum % 3 != 0){
    cout << -1;
    return 0;
}

2. 前导零问题

// 错误：从小到大输出
for(int j = 0; j <= 9; j++){...}

// 正确：从大到小输出
for(int j = 9; j >= 0; j--){...}

总结

这道题考查了：

数论知识： 375的因数分解和整除性质
贪心思想： 优先选择能组成更大数的后缀
实现技巧： 临时减法、避免前导零等
细节处理： 数字计数、边界情况等

关键是要理解375 = 3 × 125，然后分别处理被3整除和被125整除的条件。通过枚举所有可能的125倍数后缀，找到第一个可行的解即可。

题解 | #小红的375#