小红的375（思维+数学）

小红的375（思维+数学）"/>

小红的375（思维+数学）

题目链接：登录—专业IT笔试面试备考平台_牛客网牛客网是互联网求职神器，C++、Java、前端、产品、运营技能学习/备考/求职题库，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

100002

输出

120000

说明

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

思路：375 = 3*125

所以我们可以知道：首先要是3的倍数才行，所以先判断一下所有位数的和是不是3的倍数。然后再判断是不是125的倍数，而125的倍数只需要判断末位3位数即可，如果可以凑出{"000","500","250","750","125","375","625","875"} 这里面任意一种，就说明是可以的。

注意：3075 我们需要的是3750而不是0375。所以我们把有0的放到前面判断就可以了，这样可以保证没有前导0。

如果可以凑出，最后的结果可以从大到小输出，再加上凑出的数即可。

上代码：

#include <bits/stdc++.h>
using namespace std;
map<char,int> mp;
string check[8]= {"000","500","250","750","125","375","625","875"};
bool flag = false;
int main() {string s;cin >> s;int sum=0;for (int i = 0; i < s.size(); i++){sum += s[i]-'0';mp[s[i]]++;}if(sum%3!=0){puts("-1");return 0;}for (int i = 0; i < 8; i++){for (int j = 0; j < 3;j++){mp[check[i][j]]--;}int k = 0;for (k = 0; k <= 9;k++){if(mp[k+'0'] < 0 ){break;}}if(k==10){for (int j = 9; j >= 0;j--) {while(mp[j+'0']>0){cout << j;mp[j+'0']--;}}cout << check[i] << endl;flag = true;break;}for (int j = 0; j < 3;j++){mp[check[i][j]]++;}}if(!flag){puts("-1");}return 0;
}