首页 > 代码库 > CodeForces 214B Hometask
CodeForces 214B Hometask
本题求n个数组成的大数,要求是2,3,5的倍数。
因为是2 和5 的倍数,所以个位为 0;所以若n个数中没有0,直接输出-1;
难点就是要求为3 的倍数。
因为若某个数为3的倍数,则其各位数的和必然是3的倍数。
当n个数的和为3的倍数时从大到小输出便可;
当n个数的和不为3的倍数时,若n个数中有模3余数与和模3余数相同时,去掉其中最小的,否则去掉两个模3余数不为0且与和模3余数不同的数中最小的。若没有这些数,输出-1;
注意当结果为0时,不能输出前导0;
ps:开始写了一个很复杂的代码,后来看过大牛们60ms的算法后又敲了一遍。。。结果还有92ms。给大牛跪了 orz ~~o(>_<)o ~~
附:(第二遍稍简洁代码)
#include <iostream>
#include <cstring>
using namespace std;
int main (){
int n;
int sign[5];
int num[20];
int sum;
while (cin>>n){
sum=0;
sign[0]=sign[1]=sign[2]=100;
memset (num,0,sizeof num);
for (int i=0;i<n;i++){
int x;
cin>>x;
num[x]++;
sum+=x;
sign[x%3]=min (sign[x%3],x);
}
if (num[0]==0){ //n个数中没有0;
cout<<-1<<endl;
continue ;
}
if (sum%3){
if (sign[sum%3]==100){
int temp=2;
for (int i=0;i<10;i++){//cout<<i<<" "<<num[i]<<endl;
if (i%3!=0&&num[i]){
num[i]--;
temp--;
n--; //为末尾去前导零准备;
}
if (i%3!=0&&num[i]){
num[i]--;
temp--;
n--;
}
if (temp==0)
break ;
}
if (temp){
cout<<-1<<endl;
continue ;
}
}
else num[sign[sum%3]]--,n--;
}
if (num[0]==n){ //若结果为0,不能输出前导零;
cout<<0<<endl;
continue ;
}
for (int i=9;i>=0;i--)
while (num[i]--)
cout<<i;
cout<<endl;
}
return 0;
}
附:(第一遍复杂代码)
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 100000+10
using namespace std;
int sum,ans;
int n;
int sign[5];
int a[maxn];
int main (){
while (cin>>n){
sum=0;
sign[0]=sign[1]=sign[2]=100;
for (int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
int temp;
temp=a[i]%3;
if (temp){
sign[temp]=min (sign[temp],a[i]);
}
}
sort (a,a+n);
if (a[0]!=0){
cout<<"-1"<<endl;
continue ;
}
if (sum%3==0){
int flag=0;
for (int i=n-1;i>=0;i--){
if (flag==0&&a[i]==0)
break ;
cout<<a[i];
flag=1;
}
if (flag==0)
cout<<"0";
cout<<endl;
continue ;
}
else if (sum%3==1){
if (sign[1]==100){
int temp=2;
for (int i=0;i<n;i++){
if (a[i]%3==2){
a[i]=100;
temp--;
}
if (temp==0)
break ;
}
if (temp){
cout<<"-1"<<endl;
continue ;
}
int flag=0;
for (int i=n-1;i>=0;i--){
if (a[i]==100)
continue ;
if (flag==0&&a[i]==0)
break ;
cout<<a[i];
flag=1;
}
if (flag==0)
cout<<"0";
cout<<endl;
}
else {
int temp=1;
int flag=0;
for (int i=n-1;i>=0;i--){
if (a[i]==sign[1]&&temp){
temp=0;
continue ;
}
if (flag==0&&a[i]==0)
break ;
cout<<a[i];
flag=1;
}
if (flag==0)
cout<<"0";
cout<<endl;
}
}
else if (sum%3==2){
if (sign[2]==100){
int temp=2;
for (int i=0;i<n;i++){
if (a[i]%3==1){
a[i]=100;
temp--;
}
if (temp==0)
break ;
}
if (temp){
cout<<"-1"<<endl;
continue ;
}
int flag=0;
for (int i=n-1;i>=0;i--){
if (a[i]==100)
continue ;
if (flag==0&&a[i]==0)
break ;
cout<<a[i];
flag=1;
}
if (flag==0)
cout<<"0";
cout<<endl;
}
else {
int temp=1;
int flag=0;
for (int i=n-1;i>=0;i--){
if (a[i]==sign[2]&&temp){
temp=0;
continue ;
}
if (flag==0&&a[i]==0)
break ;
flag=1;
cout<<a[i];
}
if (flag==0)
cout<<"0";
cout<<endl;
}
}
}
return 0;
}