链接:
http://poj.grids.cn/practice/2804/
这也是一个很简单的题目,大家一看都知道用什么方法了,当然如果是查找的话,顺序查找是不行的,
方法一,是用map,建立个map<string, string>的字典,注意不要想当然用map<char*, char*>,
那样得动态分配内存,或者还是先开个大数组存好字典,其结果还是多浪费了内存...
排序+二分也不错的,因为数据量确实很大,而且题目也建议用c的io输入,所以这样再建立map<string, string>
中间还得转换一下...
总之做这个题还是很顺利的,就wa了一次,原因是2分写错了,我也很久没在oj上写2分了...
代码如下:
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#define MAX_WORD_LEN 11
#define MAX_DICTION_ITEM (100000 + 10)
using std::sort;
struct Dictionary
{
char szWord[MAX_WORD_LEN];
char szEnglish[MAX_WORD_LEN];
};
Dictionary diction[MAX_DICTION_ITEM];
bool CmpDictionItem(Dictionary one, Dictionary two)
{
return strcmp(one.szWord, two.szWord) < 0;
}
int FindEnglish(
char* pszWord,
int nItemNum)
{
int nBeg = 0, nEnd = nItemNum - 1;
int nCmp = 0;
while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd) / 2;
nCmp = strcmp(pszWord, diction[nMid].szWord);
if (nCmp == 0)
{
return nMid;
}
else if (nCmp < 0)
{
nEnd = nMid - 1;
}
else {
nBeg = nMid + 1;
}
}
return -1;
}
int main()
{
char szStr[30];
char szWord[MAX_WORD_LEN];
int nCount = 0;
int nAnsItem = 0;
while (fgets(szStr, 29, stdin), szStr[0] != '\n')
{
sscanf(szStr, "%s%s", diction[nCount].szEnglish, diction[nCount].szWord);
++nCount;
}
sort(diction, diction + nCount, CmpDictionItem);
while (scanf("%s", szWord) == 1)
{
if ((nAnsItem = FindEnglish(szWord, nCount)) != -1)
{
printf("%s\n", diction[nAnsItem].szEnglish);
}
else {
printf("eh\n");
}
}
return 0;
}
其实我的主要目的是为了指出二分的写法,大家看我的FindEnglish函数,传递的是数组的地址和数组的长度,
然后我写函数体的时候用的是[]的形式,就是下确界,上确界,这样最重要的是需要考虑循环的条件是<还是
<=,其实这也很好判断,因为上界和下界都能够取到,所以=是成立的...而且修改right的时候,必须将right = mid - 1,
原因也是因为这是上确界,
但是如果是上不确界了,那么等号就必须去掉,而且right也只能修改为mid,因为mid-1就是确界了,而mid才是上不确界...
想到这个程度的话,以后写只有唯一解二分就应该不会出错了...但是写查找满足条件的最大或者最小解的二分还需要其它技巧...