洛谷 P7174 [COCI2014-2015#4] CESTA

[COCI2014-2015#4] CESTA

题目描述

Mirko 发现了一个正整数 $n$，由于 Mirko 喜欢数字 $30$，他想知道用 $n$ 的每位数字所组成的数中 $30$ 的最大倍数。

写一个计算这个数字的程序（如果不存在，则输出 -1）。

输入格式

一个数 $n$。

输出格式

仅一行，即题中所求。

样例 #1

样例输入 #1

30
1

样例输出 #1

30
1

样例 #2

样例输入 #2

102
1

样例输出 #2

210
1

样例 #3

样例输入 #3

2931
1

样例输出 #3

-1
1

提示

数据规模与约定

对于 $100\%$ 的数据，$n$ 的位数不超过 $10^5$。

说明

题目译自 COCI2014-2015 CONTEST #4 T1 CESTA。

分析：

首先，如果要使输入的这个数排序后是30的倍数，那么必须满足一下两个条件：
1.这个数至少含有1个0
2.这个数各位之和必须是3的倍数

所以，我们可以把输入的数看做一个字符串，然后一位一位地去找，如果当前这位是0，bo变为1.每次将这一位的数字加入ans里面。最后从大到小排个序输出就可以啦~~

代码：

#include 

using namespace std;

string s;

int ans;

bool bo;

bool cmp(char x,char y)
{
	return x>y;
}

int main() 
{
    cin>>s;
    
    for(int i=0;i<s.size();i++)
    {
		if(s[i]=='0')
		{
			bo=1;
		}
		
		ans+=s[i]-'0';
	}
	
	if(ans%3!=0||bo==0)//如果不满足任意一个条件
	{
		cout<<-1;//无解
		
		return 0;
	}
	
	sort(s.begin(),s.end(),cmp);//排序
	
	cout<<s;//输出
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

结束啦~~~