Python3 解法, 执行用时: 232ms, 内存消耗: 7256K, 提交时间: 2022-09-24 15:00:17

s = input()
a = [0 for i in range(10)]
ss = 0
for i in s:
    a[int(i)]+=1
    ss+=int(i)
if ss%3!=0:
    print(-1)
    exit(0)
if a[0]>=3:
    for i in range(9,0,-1):
        print((str)(i)*a[i],end='')
    print('0'*a[0])
    exit(0)
t = 125
while t<1000:
    g = t
    f = True
    while g>0:
        if a[g%10]==0:f = False
        a[g%10]-=1
        g//=10
    if f:
        break
    g = t
    while g>0:
        a[g%10]+=1
        g//=10
    t+=125
if f:
    for i in range(9,0,-1):
        print((str)(i)*a[i],end='')
    print(t,end='')
    print('0'*a[0])
else:print(-1)

C++ 解法, 执行用时: 13ms, 内存消耗: 1044K, 提交时间: 2021-12-07 15:25:29

#include<iostream>
using namespace std;

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

int main()
{
	int b[1010];
	string s;
	cin>>s;
	if(s.size()>300000)return -1;
	int sum=0,i,j;
	for(i=0;i<s.size();i++)
	{
		b[s[i]-'0']++;
		sum+=s[i]-'0';
	}
	if(sum%3!=0){cout<<-1;return 0;}
	for(int i=0;i<8;i++)
	{
		for(j=0;j<3;j++)b[a[i][j]-'0']--;
		for(j=0;j<=9;j++)
		{
			if(b[j]<0)break;
		}
		if(j==10)
		{
			for( j=9;j>=0;j--)while(b[j])cout<<j,b[j]--;
			cout<<a[i];
			return 0;
		}
		for(j=0;j<3;j++)
		{
			b[a[i][j]-'0']++;
		}
	}
	cout<<-1;
	return 0;
}