学步园

又被水题虐了。。。。。。给你一堆士兵的等级，等级高的的士兵可以当等级小的士兵的师傅，一个士兵最多一个师傅（可以没有），一个师傅最多1个徒弟（可以没有），如果是师徒关系，可以用一把扫帚练习技能，问你如果全部士兵都用过扫帚练习时最小需要的扫帚数量。刚开始打算直接贪心的。。复杂度太高，tle了，，然后百度才发现所求的竟然就是出现最多的那一个数，即最长平台.用map做其实爆简单。。。

code:

#include <map>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAXN = 50000;
int n,ans,num;
//字典树数字版
struct tire
{
    int cnt;
    tire *next[10];
    tire()
    {
        cnt=0;
        memset(next,NULL,sizeof(next));
    }
}tires[MAXN];

int solve(char *str)
{
    int i;
    int len=strlen(str);
    for(i=0;i<len;i++)
    {
        if(str[i]!='0')
        {
            break;
        }
    }
    return i;
}

void insert(int start,char *str)
{
    tire *p=&tires[0];
    int i,tmp;
    int len=strlen(str);
    for(i=start;i<len;i++)
    {
        tmp=str[i]-'0';
        if(p->next[tmp]==NULL)
        {
            p->next[tmp]=&tires[++num];
        }
        p=p->next[tmp];
    }
    p->cnt++;
    //printf("cnt---%d\n",p->cnt);
    if((p->cnt)>ans)
    {
        ans=p->cnt;
    }
}


char str[33];
int main()
{
    int i,start;
    while(~scanf("%d",&n))
    {
        ans=1;
        num=0;
        memset(tires,NULL,sizeof(tires));
        for(i=1;i<=n;i++)
        {
            scanf("%s",str);
            start=solve(str);
            insert(start,str);
        }
        printf("%d\n",ans);
    }
    return 0;
}