鏈接:
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才是上不確界...
想到這個程度的話,以后寫只有唯一解二分就應該不會出錯了...但是寫查找滿足條件的最大或者最小解的二分還需要其它技巧...