魔咒词典为什么总是WA

魔咒词典为何总是WA？
直接上题与链接。
http://acm.hdu.edu.cn/showproblem.php?pid=1880

Input
首先列出词典中不超过100000条不同的魔咒词条，每条格式为：
[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。

Output
每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”

我的方法中，
1、使用两个数组，分别存储按魔咒字典顺序排列和按对应功能字典顺序排列的的字符串，
2、根据出现的字符串类型，使用不同的搜索依据，使用的方法都是折半查找方法。

问题就是，始终在OJ中都是WA，不太明白是哪个位置输出不对了。
麻烦各位帮帮忙~ 感谢各位~

测试数据：
Sample Input
[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

Sample Output
light the wand
accio
what?
what?

以下是代码：



#include <stdio.h>

#include <algorithm>

#include <string.h>

using namespace std;

typedef struct

{

	char magic[25];

	char func[85];

}NODE;



NODE words[100000+3]; 

NODE words2[100000+3];



bool cmp1(NODE a ,NODE b)

{

	return strcmp(a.magic, b.magic) <0;

}


bool cmp2(NODE a,NODE b)

{

	return strcmp(a.func, b.func) < 0;

}


//折半查找 搜索字符串 

void search(char s[], int l , int r , int tag)

{

	if( l >  r)

	{

		printf("what?\n");

		return ;

	}

	int m = (l+r)/2;

	//magic --> fun

	if( tag == 1)

	{

		if( strcmp(words[m].magic , s) < 0 )

			search(s, m+1, r , tag);

		else if(strcmp(words[m].magic , s) > 0 )

			search(s, l , m-1, tag);

		else

			printf("%s\n",words[m].func);		

	}

	else

	{

		if( strcmp(words2[m].func, s ) < 0)

			search(s, m+1, r, tag);

		else if(strcmp( words2[m].func, s) > 0 )

			search(s, l , m-1, tag);

		else

			printf("%s\n",words2[m].magic);

	}

}



int main()

{

	char in[120];

	char deal[120];

	int t=0;

	while( gets(in) && strcmp(in, "@END@") != 0)//

	{

		// if not, there will be a '\n' rest. and the result of 'scanf' will be 0

		//fflush(stdin);

		sscanf(in,"%[^]]",deal);		

		strcpy(words[t].magic, deal+1);

		strcpy(words[t].func, in+strlen(deal)+2);

		strcpy(words2[t].magic, deal+1);

		strcpy(words2[t++].func, in+strlen(deal)+2);		

	}	

	//排序 

	sort(words, words+t,cmp1);

	sort(words2,words2+t, cmp2);


	int i,n;

	scanf("%d",&n);

	fflush(stdin);

	while(n--)

	{

		gets(in);

		if( in[0] == '[')

		{			

			in[strlen(in)-1] = '\0';

			search(in+1, 0,t-1,1);			

		}

		else

		{

			search(in, 0,t-1,2);		

		}		

	}	

	return 0;

}

------解决方案--------------------

不要使用

while (条件)

更不要使用

while (组合条件)

要使用

while (1) {

 if (条件1) break;

 //...

 if (条件2) continue;

 //...

 if (条件3) return;

 //...

}

因为前两种写法在语言表达意思的层面上有二义性，只有第三种才忠实反映了程序流的实际情况。

典型如：

下面两段的语义都是当文件未结束时读字符

while (!feof(f)) {

 a=fgetc(f);

 //...

 b=fgetc(f);//可能此时已经feof了！

 //...

}

而这样写就没有问题：

while (1) {

 a=fgetc(f);

 if (feof(f)) break;

 //...

 b=fgetc(f);

 if (feof(f)) break;

 //...

}

类似的例子还可以举很多。

------解决方案--------------------
以下2行多输出了逗号:
printf("%s,\n",(*q).func);
printf("%s,\n",(*q).magic);
------解决方案--------------------
5楼代码改以下3行可AC：

  getchar();//改 fflush(stdin);

        printf("%s\n",(*q).func); //改 printf("%s,\n",(*q).func);

        printf("%s\n",(*q).magic); //改 printf("%s,\n",(*q).magic);

魔咒词典 为什么总是WA

相关推荐