【牛客】小红的375（数学+模拟思维）

【牛客】小红的375（数学+模拟思维）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

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

输入描述:

一个正整数，大小不超过 10^{300000}

输出描述:

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

示例1

输入

100002

输出

120000

说明

输出201000等答案也是可以通过的。
但012000是不合法的，因为它包含了前导零。输出123000、222000也是不合法的，因为它不是原正整数的重排。输出200100也是不合法的，因为它不是375的倍数。

---

解题思路：

本以为是道数论的题目想跳过去，但其实在纸上划拉一下发现并不难，就是一道思维题目 ，整除375就是整除125*3，整除三好说，小学数学知识，就看把每一位数加起来是不是可以整除3就可以，整除125，对于一个很大的数的话我们可以其实只需看最后三位数就可以（也就是前几位数*1000+后三位数）， 枚举出八种情况{"000","500","250","750","125","375","625","875"}，然后枚举每种情况存不存在，我们可以用map实现，枚举成功后为了避免前导的0我们就倒序输出就可以了，最后如果枚举失败输出-1就行了

详细的看下面ac代码

#include 
using namespace std;
string s;
string check[8]= {"000","500","250","750","125","375","625","875"}; //枚举每种情况
map m;
int main()
{
    cin>>s;
    int cur=0;
    for(int i=0;i < s.size();i++)
    {
        cur+=s[i]-'0';  //将各个位的数加起来
        m[s[i]]++;
    }
    if(cur%3!=0){   //判断是否整除3
        cout<<-1<=0;r--)
            {
                //输出
                while(m[r+'0']>0){
                    cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702633.html