我用搜索的方法写了个程序，这肯定是不行的，必然超时，，，
#include <iostream>
using namespace std;
class Group
{
public:
	char Letter;
	int num;
    Group *nextGroup;
	Group()
	{
		Letter=NULL;
		num=0;
		nextGroup=NULL;
	};
};
Group *pheadGroup;//头指针指向第一个元素,头指针中没有存放字母
Group *pGroup;
int M=0;
void InputData()
{
	pheadGroup=pGroup=new Group();
	char ch;
	getchar();
	while(true)
	{
		ch=getchar();
		if(ch==10)break;
		if(ch!=pGroup->Letter)
		{
			   pGroup->nextGroup=new Group();
			   pheadGroup->num++;//头结点中的num用来记录有多少个group
			   pGroup=pGroup->nextGroup;
			   pGroup->Letter=ch;
			   pGroup->num++;
		}
		else if(ch==pGroup->Letter)
			pGroup->num++;  
	}
	return ;
}
void check_explode()  //当pGroup指向的group中加了一个ball
{
	if(pGroup->num >= M)
	{
		Group*p=pheadGroup;
		while(p->nextGroup!=pGroup) //p指向pGroup的前一个节点
			  p=p->nextGroup;
		p->nextGroup=pGroup->nextGroup;//删除当前pGroup节点
		delete(pGroup);
		while( (p->nextGroup!=NULL)&&(p!=pheadGroup)&&( p->Letter==p->nextGroup->Letter))
		{ 
			//合并两个节点
			p->num  =  p->num + p->nextGroup->num;
			Group*temp   = p->nextGroup;
			p->nextGroup = temp->nextGroup;
			delete(temp); //删除p先前的后继节点
			if(p->num >= M)
			{
				Group*pp=pheadGroup;
			    while(pp->nextGroup!=p)  //pp指向p节点的前继节点
				      pp=pp->nextGroup;
				pp->nextGroup=p->nextGroup;//删除p节点
				delete(p);
				p=pp;
			}
		}
	}
	return ;
}
void back_trace(int&step,int& minstep)//回溯
{
   
	    if(step >(pheadGroup->num*M-M))return ;
		if(pheadGroup->nextGroup==NULL)
		{
			if(step<minstep)
				minstep=step;
			return;
		}
   pGroup=pheadGroup->nextGroup;
	while(pGroup!=NULL && step<minstep )
	{
		int tempstep=step;
		step++;
	    //在调整前，应该将当前状态保存起来
	   Group* temphead=new Group();
	   temphead->num=pheadGroup->num;
	   Group* temppGroup;
	   Group* p=pheadGroup->nextGroup;
	   Group* tp=temphead ;
	    while(p!=NULL)
	         {
				 tp->nextGroup=new Group();
				 tp=tp->nextGroup; 

				 tp->Letter=p->Letter;
				 tp->num=p->num;
				 if(pGroup==p)
				 {
					temppGroup=tp;
				 }
				 p=p->nextGroup;	 
	         }
		
		pGroup->num++;  //向当前组发射一颗炮弹
		check_explode();//检测是否会引起爆炸，如果有则要做相应的调整,
		if(step<minstep)
		    back_trace(step,minstep); //继续回溯
		p=pheadGroup;
		while(p!=NULL)
		{
			Group*t = p;
			p = p->nextGroup;
			delete(t);
		}
		//恢复状态
		step=tempstep;
		pheadGroup=temphead;
		pGroup=temppGroup;
		pGroup=pGroup->nextGroup;
	}

}
int main()
{
	while(cin>>M)
	{
	    InputData();
	    int step=0,minstep=pheadGroup->num*M;
	    back_trace(step,minstep);
	    cout<<minstep<<endl;
	/*
	pGroup=pheadGroup->nextGroup;
	while(pGroup!=NULL)
	{
		cout<<pGroup->Letter<<"  "<<pGroup->num<<endl;
		pGroup=pGroup->nextGroup;
	}
	*/
	}
	return 0;
}