stlinacm-文庫(kù)吧
2025-07-29 14:29 本頁(yè)面
【正文】 gn) 找不到返回 () lower_bound() O(logn) 查找第一個(gè)不小于 k的元素 upper_bound() O(logn) 查找第一個(gè)大于 k的元素 equal_range() O(logn) 返回 pairlower,upper multiset 允許重復(fù)元素 用法 : struct SS {int x,y。}。 struct ltstr { bool operator() (SS a, SS b) {return 。} }。 int main() { set SS, ltstr st。 … } UVA 105 The Skyline Problem 給定一些樓房的范圍和高度，求出他們的輪廓。 Input: 1 11 5 2 6 7 3 13 9 12 7 16 14 3 25 19 18 22 23 13 29 24 4 28 Output: 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 維護(hù)一個(gè) BST，可以得到復(fù)雜度 O(nlogn)的算法 可以使用 multiset簡(jiǎn)化編程 Code here ? map 內(nèi)部實(shí)現(xiàn) : pairkey,value組成的紅黑樹(shù) mapKey, Data, Compare, Alloc insert() O(logn) erase() O(logn) find() O(logn) 找不到返回 () lower_bound() O(logn) 查找第一個(gè)不小于 k的元素 upper_bound() O(logn) 查找第一個(gè)大于 k的元素 equal_range() O(logn) 返回 pairlower,upper [key]運(yùn)算符 O(logn) *** multimap 允許重復(fù)元素 , 沒(méi)有 []運(yùn)算符 TOJ 1378 Babelfish Code: () include cstdio include string include map using namespace std。 map string,string mp。 int main() { char buf[100],s1[100],s2[100]。 while (gets(buf)) { if (strlen(buf) == 0) break。 sscanf(buf,%s%s,s1,s2)。 mp[(string)s2] = (string)s1。 } … … while (gets(buf)) { if (((string)buf) != ()) printf(%s\n,mp[(string)buf].c_str())。 else printf(eh\n)。 } return 0。 } A challenge: TOJ 2175 Computer Games ? priority_queue 內(nèi)部實(shí)現(xiàn) : 堆 priority_queueT, Sequence, Compare 支持操作 : push() O(logn) pop() O(logn) top() O(1) See also: push_he
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1