timus 1067 Disk Tree【超时代码】

题目的描述链接timus 1067

这个题目困扰了很久，后面理清思路了,解法也很明确,结果是超时!

在写代码时也收获了一些:

在把思路理好后去写代码会更顺利点,边想思路边写代码效率比较低!

先把代码放在这里,超时的代码不好说什么,以后还可以学到一些东西!第一次用new 和delete,比较怂!(2.046s>2.0s TLE)

#include<iostream>
#include<algorithm>
using namespace std;
struct Disk
{
	int num; //该文件夹的编号 排序时候有用
	int sonnum; //子节点的数目
	int son[120]; //子节点对应的编号
	char s[10];  //自身文件夹名
};
Disk d[20002],root[505];
int index[505],id;  //最顶层对应的编号,最顶层编号数
int n,dnum;  //文件路径数 文件夹个数
char s[100];  //文件路径
int search(char *q,int num)
{
	int i;
	if(num==-1)
	{
		for(i=0;i<id;i++) 
		{
			if(strcmp(d[index[i]].s,q)==0)return index[i];  //返回最顶层文件夹的编号
		}
		return dnum;  
	}
	else  //在对应编号的文件夹中找是否有和自己文件夹名称相同的文件夹号
	{
		for(i=0;i<d[num].sonnum;i++)
		{
			if(strcmp(q,d[d[num].son[i]].s)==0)return d[num].son[i];  //返回子文件夹的编号
		}
		return dnum;
	}
}
void input()
{
	int i,j;
	for(i=0;i<n;i++)
	{
		char tmp[100];
		scanf("%s",s);
		bool f=false;   //判断每次首个文件夹时为false
		int kt=0,rnum;  //表示在第rnum文件夹的目录或子目录下
		for(j=0;j<strlen(s);j++)
		{
			if(s[j]=='\\'&&f==false)
			{
				tmp[kt]='\0';
				rnum=search(tmp,-1);
				if(rnum==dnum)  //最顶层文件夹没有一个匹配，就新加一个顶层文件夹
				{
					d[dnum].num=dnum;
					strcpy(d[dnum].s,tmp);
					d[dnum].sonnum=0; //子节点个数为初始化0
					index[id++]=dnum;
					dnum++;
				}
				kt=0;
				f=true;
			}
			else if(s[j]=='\\')
			{
				tmp[kt]='\0';
				int rtmp=search(tmp,rnum);
				if(rtmp==dnum)  //已有的子文件夹里没有找到该文件夹的名称，就新加一个文件夹
				{
					d[rnum].son[d[rnum].sonnum]=dnum;
					strcpy(d[dnum].s,tmp);
					d[dnum].num=dnum;
				    d[dnum].sonnum=0;
					d[rnum].sonnum++;
					dnum++;
				}
				rnum=rtmp;
				kt=0;
			}
			else tmp[kt++]=s[j];
		}
		tmp[kt]='\0';
		if(f==false)
		{
			rnum=search(tmp,-1);
			if(rnum==dnum)  //最顶层文件夹没有一个匹配，就新加一个顶层文件夹
			{
				d[dnum].num=dnum;
				strcpy(d[dnum].s,tmp);
				d[dnum].sonnum=0; //子节点个数为初始化0
				index[id++]=dnum;
				dnum++;
			}
		}
		else
		{
			int rtmp=search(tmp,rnum);
			if(rtmp==dnum)  //已有的子文件夹里没有找到该文件夹的名称，就新加一个文件夹
			{
				d[rnum].son[d[rnum].sonnum]=dnum;
				strcpy(d[dnum].s,tmp);
				d[dnum].num=dnum;
			    d[dnum].sonnum=0;
				d[rnum].sonnum++;
				dnum++;
			}
		}
	}
}
bool cmp(Disk aa,Disk bb) //定义排序规则 按字典序从小到大排序
{
	return strcmp(aa.s,bb.s)<0;
}
void dfs(int nnum,int level)  //从第一层子目录开搜，排序后输出
{
	int i,j;
	if(d[nnum].sonnum)
	{
		Disk *w=new Disk[505];
		for(i=0;i<d[nnum].sonnum;i++)
		{
			w[i]=d[d[nnum].son[i]];
		    //printf("1: %s\n",w[i].s);
		}
		sort(w,w+d[nnum].sonnum,cmp);
		for(i=0;i<d[nnum].sonnum;i++)
		{
			for(j=0;j<level;j++)printf(" ");
			printf("%s\n",w[i].s);
			//printf("%s\n",d[d[nnum].son[i]].s);
			int x=w[i].num;
			//dfs(d[nnum].son[i],level+1);
			dfs(x,level+1);
		}
		delete [] w;
	}
}
int main()
{
	while(scanf("%d",&n)!=-1)
	{
		id=0;
		dnum=0;
		input();
		int i,j;
	    for(i=0;i<id;i++)
		    root[i]=d[index[i]];
	    sort(root,root+id,cmp);
		//sort(d,d+dnum,cmp);
		for(i=0;i<id;i++)
		{
			int num=root[i].num;
		    printf("%s\n",root[i].s);
		    dfs(num,1);
		}
	}
	return 0;
}

timus 1067 Disk Tree【超时代码】

原文：http://blog.csdn.net/quanqiuzhongzi/article/details/42208207