UVa 10282

題目

http://domen111.github.io/UVa-Easy-Viewer/?10282

題目會先給你每個英文字對應到的外國文字，這群對應的字保證是一對一，形成一個字典

接下來會有多筆詢問，輸入一個外國文字，輸出相對應的英文字，如果不存在則輸出 eh

想法

這題可以直接用 map 對應，但是這裡我們用二分搜來實作看看

首先先把字典建立好，可以用一個 struct 來建立每個英文字對應到的外國字，接下來排序，方便我們查詢

最後用二分搜就可以了

Code

//By Koios1143
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;
int i=0, res, res2;
string s, key, value, q;

struct word{
	string key;
	string value;
};
word dict[100010];

bool cmp(word p, word q){
	if(p.value != q.value) return p.value < q.value;
	return false;
}

int search(int l, int r, string p){
	while(l!=r){
		int mid = (l+r)/2;
		if(dict[mid].value == p) return mid;
		if(dict[mid].value < p) l = mid+1;
		else r=mid;
	}
	return -1;
}

int main(){
	while(getline(cin, s) && s!=""){
		// 因為輸入是用換行間格，一次讀取一整行比較好判斷
		// 接下來用 stringstream 分割字串
		stringstream ss;
		ss<<s;
		ss>>key>>value;
		dict[i].key = key;
		dict[i].value = value;
		i++;
	}
	sort(&dict[0], &dict[i], cmp);
	while(cin>>q){
		res = search(0, i, q);
		if(res == -1) cout<<"eh\n";
		else cout<<dict[res].key<<"\n";
	}

	return 0;
}

時間複雜度分析

假設有 $N$ 筆輸入以及 $Q$ 筆詢問

輸入時間複雜度為 $O(N)$

排序時間複雜度為 $O(NlogN)$

搜尋時間複雜度為 $O(QlogN)$

總時間複雜度為 $O(N + (N+Q)logN)$