鏈接:
http://poj.grids.cn/practice/2804/
這也是一個(gè)很簡(jiǎn)單的題目,大家一看都知道用什么方法了,當(dāng)然如果是查找的話,順序查找是不行的,
方法一,是用map,建立個(gè)map<string, string>的字典,注意不要想當(dāng)然用map<char*, char*>,
那樣得動(dòng)態(tài)分配內(nèi)存,或者還是先開(kāi)個(gè)大數(shù)組存好字典,其結(jié)果還是多浪費(fèi)了內(nèi)存...
排序+二分也不錯(cuò)的,因?yàn)閿?shù)據(jù)量確實(shí)很大,而且題目也建議用c的io輸入,所以這樣再建立map<string, string>
中間還得轉(zhuǎn)換一下...
總之做這個(gè)題還是很順利的,就wa了一次,原因是2分寫(xiě)錯(cuò)了,我也很久沒(méi)在oj上寫(xiě)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;
}
其實(shí)我的主要目的是為了指出二分的寫(xiě)法,大家看我的FindEnglish函數(shù),傳遞的是數(shù)組的地址和數(shù)組的長(zhǎng)度,
然后我寫(xiě)函數(shù)體的時(shí)候用的是[]的形式,就是下確界,上確界,這樣最重要的是需要考慮循環(huán)的條件是<還是
<=,其實(shí)這也很好判斷,因?yàn)樯辖绾拖陆缍寄軌蛉〉?所以=是成立的...而且修改right的時(shí)候,必須將right = mid - 1,
原因也是因?yàn)檫@是上確界,
但是如果是上不確界了,那么等號(hào)就必須去掉,而且right也只能修改為mid,因?yàn)閙id-1就是確界了,而mid才是上不確界...
想到這個(gè)程度的話,以后寫(xiě)只有唯一解二分就應(yīng)該不會(huì)出錯(cuò)了...但是寫(xiě)查找滿足條件的最大或者最小解的二分還需要其它技巧...