题解 SP416 【DIV15 - Divisibility by 15】
这是一道标准的贪心题目。
首先我们想一下，一个数要想整除15，它必须满足的条件是什么呢？很显然，它必须既能整除3，又能整除5，所以这道题就分成了两个部分：
1、整除3，就必须满足所有数位之和能够整除3；
2、整除5，就必须满足末位只能是0或5。
既然是贪心取最大数的问题，所以我们可以把这个数字序列从大到小排列下来，例如014312排列成432110，然后逐步删除数字即可。
我们先考虑整除3的情况，对于任何数字无非只有3种情况：
1、mod3=0，说明序列本身就可以整除3，那太好了，一个数也不用删；
2、mod3=1，为了让序列能够整除3，我们有两个选择：删除一个mod3=1的数，或者删除两个mod3=2的数。当然为了贪心，我们肯定力求少删，但是如果整个序列不存在mod3=1的数的话，就只能删除2个mod3=2的数了；
3、mod3=2，道理和上面那条一样，可以选择删除一个mod3=2的数，或者删除两个mod3=1的数，但是如果这个情况你这么写，就会迎来一个红红的刺眼的wa。
看到这里你愣了，这不是挺对的吗，为啥wa啊？那么我给出一个数据：158。大家用肉眼就能看出来，显然15就是最后的解。但是根据我们上述的逻辑，1+5+8=14，14%3=2所以是第3条，然后我们就会优先删除一个mod3=2的数：5，这样5上来就给删掉了，那么最后的结果自然会输出impossible。
所以当我们进入第三条 序列mod3=2的情况时，首先我们先分类讨论一下：
1、序列有没有0？如果有0，那么258随便删，反正有0在结尾压轴；
2、如果没有0，只有5，那么剩下mod3=2的数还有几个（包括这个5）？如果有2个及以上，那么就删掉除了这个5以外的那个最小的mod3=2的数。
3、如果剩下mod3=2的数只剩下这个5了，抱歉，只能采用删除两个mod3=1的数，不然的话无法满足整除5的条件了。
最后在输出的时候检测一下是否合理，再修改一些细节上的问题，就ok了。注意如果序列中没有0，那么必须留一个5放在末位。
#include <iostream>
#include <string.h>
using namespace std;
char ch[2005];
int numcnt[10];
int len,total=0,mod1cnt=0,mod2cnt=0;
void delmod1(int times)
{
while(times--)
{
for(int i=1;i<8;i+=3)
{
if(numcnt[i])
{
numcnt[i]--;
len--;
mod1cnt--;
total-=i;
break;
}
}
}
}
void delmod2(int times)
{
while(times--)
{
for(int i=2;i<9;i+=3)
{
if(numcnt[i])
{
numcnt[i]--;
len--;
mod2cnt--;
total-=i;
break;
}
}
}
}
void check()
{
/*余3得1，优先选择消去一个mod3=1的数，不行的话选择消去两个mod3=2的数*/
if(total%3==1)
{
if(mod1cnt)
{
delmod1(1);
return;
}
else if(mod2cnt>=2)
{
if(numcnt[0])
{
delmod2(2);
return;
}
else if(numcnt[5]==0)return;
else if(numcnt[5])
{
if(mod2cnt>=2)
{
numcnt[5]--;
mod2cnt--;
delmod2(2);
numcnt[5]++;
mod2cnt++;
}
}
else return;
}
else return;
}
/*与上同理*/
else if(total%3==2)
{
if(mod2cnt)
{
/*有0的话就可以随便删258了*/
if(numcnt[0])
{
delmod2(1);
return;
}
/*没有0的话需要注意，如果5是用来放在末位的，那么不能删*/
else if(numcnt[5])
{
numcnt[5]--;
mod2cnt--;
if(mod2cnt>0)
{
/*如果还有其他mod3=2的数的话，就回溯不删5了*/
delmod2(1);
numcnt[5]++;
mod2cnt++;
return;
}
/*如果删完5发现没有其他mod3=2的数了，说明这个5是末位的5，不能删，所以回溯，进入下一个语句*/
numcnt[5]++;
mod2cnt++;
}
}
if(mod1cnt>=2)
{
delmod1(2);
return;
}
else return;
}
}
void output()
{
if(len<=0)printf("impossible");
else if(total%3)printf("impossible");
/*之前有5有0不代表现在还有5有0，所以需要再次判断*/
else if(!numcnt[0]&&!numcnt[5])printf("impossible");
else
{
if(total==0)
{
printf("0");
return ;
}
/*如果存在0，就倒序输出，这样保证末位是0，就可以整除5了*/
if(numcnt[0])
{
for(int i=9;i>=0;i--)
{
for(int j=numcnt[i];j>0;j--)printf("%d",i);
}
return ;
}
/*如果无0有5，我们需要拿出来一个5放在末位，就可以整除5了*/
if(numcnt[5])
{
for(int i=9;i>=0;i--)
{
for(int j=numcnt[i];j>0;j--)if(i!=5||j!=1)printf("%d",i);
}
printf("5");
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",ch);
/*初始化*/
total=0,mod1cnt=0,mod2cnt=0;
len=strlen(ch);
for(int i=0;i<10;i++)numcnt[i]=0;
for(int i=0;i<len;i++)numcnt[ch[i]-'0']++;
for(int i=0;i<10;i++)
{
total+=i*numcnt[i];
if(i%3==1)mod1cnt+=numcnt[i];
if(i%3==2)mod2cnt+=numcnt[i];
}
/*如果无0无5，就不能整除5，直接舍*/
if(numcnt[0]==0&&numcnt[5]==0)
{
printf("impossible\n");
continue;
}
check();
output();
printf("\n");
}
}