1. priority_queue
无理由在广搜和解决贪心问题用处很大，首先作为广搜的挑选最优状态如Astar，然后是当做堆给最短路和最小生成树做优化，用的是贪心思想。
定义优先级，和正常的反过来。
bool operator < (const number1 &a)const { return x > a.x; // 从小到大 ，x 小的 优先级别高 }优先队列的实现就是一个堆，队尾进入一个新元素就和父节点比较上升，出对就调整堆。
上一道纯贪心和优先队列完美结合的例题 HDU 4544
#include#include #include #include using namespace std;#define MAXN 100006#define LL long longint Blood[MAXN];bool cmp(int a, int b) { return a > b;}struct Node { int D, cost; bool operator <(const Node &tmp) const { return cost > tmp.cost; }} arrow[MAXN];int N, M;priority_queue Q;bool cmp_Node(Node a, Node b) { return a.D > b.D;}LL solve() { LL Min_cost = 0; int pos = 0; for (int i = 0; i < N; i++) { while (pos < M && Blood[i] <= arrow[pos].D) Q.push(arrow[pos++]); if (Q.empty()) { return -1; } Min_cost += Q.top().cost; Q.pop(); } return Min_cost;}int main() {// freopen("data_tmp.txt", "r", stdin); int i; while (~scanf("%d%d", &N, &M)) { while (!Q.empty()) Q.pop(); for (i = 0; i < N; i++) scanf("%d", &Blood[i]); for (i = 0; i < M; i++) scanf("%d", &arrow[i].D); for (i = 0; i < M; i++) scanf("%d", &arrow[i].cost); sort(Blood, Blood + N, cmp); sort(arrow, arrow + M, cmp_Node); if (arrow[0].D < Blood[0]) { puts("No"); continue; } LL ans = solve(); if (ans == -1) puts("No"); else printf("%I64d\n", ans); } return 0;}
2. set 与 hash_set
应用，首先是集合操作，交并补对称差，和查找.count() ，指向键值>=k的第一个元素.lower_bound() ，指向键值>k的第一个元素.upper_bound()，it-- 就得到<=val 的最大值。
其次是对于动态插入删除有序的题，或者维护状态（最远曼哈顿距离），可以用set快速找到应该插入的位置，如insert和lower_bound 都会返回位置的迭代器。
上一道很有代表性的set应用 (hash_set用法和set一致，很多情况下hash_set效率更高，且hash表空间分配上使用了一个近似于倍增的素数表，最开始取第一个素数，当空间不足时就使用下一个素数)
内部实现为一颗红黑树。
//给出一些能引起周围一定区域内炸弹爆炸的炸弹，按给出顺序引爆//输出每次爆炸会引起几个炸弹的爆炸//unique(）去重操作，返回去重后尾地址//lower_bound(first,last,val)求first到last区间内大于等于val第一个值#include#include #include #include #include using namespace std;const int maxn = 100015;int myhash[maxn];struct node { int x, y, d;} mine[maxn];struct node2 { int y, id; node2(int a, int b) { y = a; id = b; } bool operator<(const node2 &tmp) const { return y < tmp.y; }};multiset p[maxn];multiset ::iterator LL, RR, it;queue q;bool vis[maxn];int main() { int n; while (scanf("%d", &n) != EOF, n) { for (int i = 0; i < n; i++) { scanf("%d%d%d", &mine[i].x, &mine[i].y, &mine[i].d); myhash[i] = mine[i].x; //在 x 方向离散化 } sort(myhash, myhash + n); int cnt = unique(myhash, myhash + n) - myhash; for (int i = 0; i < cnt; i++) p[i].clear(); memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { int pos = lower_bound(myhash, myhash + cnt, mine[i].x) - myhash; p[pos].insert(node2(mine[i].y, i)); // i 是原序号 } int id; scanf("%d", &id); while (!q.empty()) q.pop(); int ans = 0; q.push(id); vis[id] = 1; while (!q.empty()) { int now_id = q.front(); //点燃第一个 q.pop(); ans++; int first_pos = lower_bound(myhash, myhash + cnt, mine[now_id].x - mine[now_id].d) - myhash; int last_pos = upper_bound(myhash, myhash + cnt, mine[now_id].x + mine[now_id].d) - myhash; //首先由横坐标确定大致的 x 寻找范围 for (int pos = first_pos; pos < last_pos; pos++) { int dy = mine[now_id].d - abs(mine[now_id].x - myhash[pos]); //lower_bound 与upper_bound配合确定上下界 LL = p[pos].lower_bound(node2(mine[now_id].y - dy, 0)); RR = p[pos].upper_bound(node2(mine[now_id].y + dy, 0)); for (it = LL; it != RR; it++) { if (vis[it->id] == 0) { vis[it->id] = 1; q.push(it->id); } } p[pos].erase(LL, RR); //删除已经爆炸的点 区间删除 } } printf("%d\n", ans); } return 0;}
3. map
首先是映射，如规定10000000000对应1，而不能开那么大的bool数组吧，那就用map就可以。
其次它有自排序功能，所以对于处理字典序很有用。
map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。
//给出一系列要忽略的单词，这些单词以外的单词都看作关键字。给出一些标题，按这些关键字的字典序给标题排序#include#include #include
4.heap
头文件 #include <algorithm>
建立堆 make_heap(_First, _Last, _Comp)
默认是建立最大堆的。对int类型，可以在第三个参数传入greater<int>()得到最小堆。
在堆中添加数据 push_heap (_First, _Last) 要先在最后加入数据，再调用push_heap()在原堆上调整
在堆中删除数据
pop_heap(_First, _Last) 要先调用pop_heap()清除第一个并调整成堆，再删除数据
堆排序 sort_heap(_First, _Last) 稳定排序
#includeusing namespace std;int num[20];void debug() { for (int i = 0; i < 11; i++) printf("%d ", num[i]); puts("");}int main() { memset(num, -1, sizeof(num)); for (int i = 0; i < 10; i++) num[i] = rand() % 100; debug(); make_heap(num, num + 10); debug(); num[10] = 100; push_heap(num, num + 11); debug(); pop_heap(num, num + 11); num[10] = -1; debug(); return 0;}
执行结果
原数组 41 67 34 0 69 24 78 58 62 64 -1
建堆后 78 69 41 62 67 24 34 58 0 64 -1 添加100调整后 100 78 41 62 69 24 34 58 0 64 67 清除堆顶调整后 78 69 41 62 67 24 34 58 0 64 -1
POJ 2051
//============================================================================// Name : Test.cpp// Author :// Version :// Copyright : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include#include using namespace std;struct Node { int id, p, time; bool operator <(const Node &tmp) const { return (time == tmp.time) ? id > tmp.id : time > tmp.time; }} node[4000];int main() { char opr[10]; int cnt = 0; while (scanf("%s", opr) && opr[0] != '#') { scanf("%d%d", &node[cnt].id, &node[cnt].p); node[cnt].time = node[cnt].p; cnt++; } make_heap(node, node + cnt); int k; scanf("%d", &k); while (k--) { printf("%d\n", node[0].id); pop_heap(node, node + cnt); node[cnt - 1].time += node[cnt - 1].p; push_heap(node, node + cnt); } return 0;}
5.string
有关函数
string类的构造函数：string(const char *s); //用c字符串s初始化string(int n,char c); //用n个字符c初始化此外，string类还支持默认构造函数和复制构造函数，如string s1；string s2="hello"；都是正确的写法。当构造的string太长而无法表达时会抛出length_error异常string类的字符操作：const char &operator[](int n)const;const char &at(int n)const;char &operator[](int n);char &at(int n);operator[]和at()均返回当前字符串中第n个字符的位置，但at函数提供范围检查，当越界时会抛出out_of_range异常，下标运算符[]不提供检查访问。const char *data()const;//返回一个非null终止的c字符数组const char *c_str()const;//返回一个以null终止的c字符串int copy(char *s, int n, int pos = 0) const;//把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中，返回实际拷贝的数目string的特性描述:int capacity()const; //返回当前容量（即string中不必增加内存即可存放的元素个数）int max_size()const; //返回string对象中可存放的最大字符串的长度int size()const; //返回当前字符串的大小int length()const; //返回当前字符串的长度bool empty()const; //当前字符串是否为空void resize(int len,char c);//把字符串当前大小置为len，并用字符c填充不足的部分string类的输入输出操作:string类重载运算符operator>>用于输入，同样重载运算符operator< <用于输出操作。函数getline(istream &in,string &s);用于从输入流in中读取字符串到s中，以换行符'\n'分开。string的赋值：string &operator="(const" string &s); 把字符串s赋给当前字符串string &assign(const char *s); 用c类型字符串s赋值string *s,int n); 用c字符串s开始的n个字符赋值string &assign(int n,char c); 用n个字符c赋值给当前字符串string &s,int start,int 把字符串s中从start开始的n个字符赋给当前字符串string &assign(const_iterator first,const_itertor last); 把first和last迭代器之间的部分赋给字符串string的连接：string &operator+="(const" 把字符串s连接到当前字符串的结尾 &append(const 把c类型字符串s连接到当前字符串结尾string 把c类型字符串s的前n个字符连接到当前字符串结尾string 同operator+="()string" pos,int 把字符串s中从pos开始的n个字符连接到当前字符串的结尾string &append(int 在当前字符串结尾添加n个字符cstring &append(const_iterator first,const_iterator 把迭代器first和last之间的部分连接到当前字符串的结尾 string的比较：bool operator="=(const" &s1,const &s2)const; 比较两个字符串是否相等运算符"> ","<",">=","<=","!="均被重载用于字符串的比较；int compare(const string &s) const;//比较当前字符串和s的大小int compare(int pos, int n,const string &s)const;//比较当前字符串从pos开始的n个字符组成的字符串与s的大小int compare(int pos, int n,const string &s,int pos2,int n2)const;//比较当前字符串从pos开始的n个字符组成的字符串与s中pos2开始的n2个字符组成的字符串的大小int compare(const char *s) const;int compare(int pos, int n,const char *s) const;int compare(int pos, int n,const char *s, int pos2) const;compare函数在>时返回1， <时返回-1，==时返回0 string的子串：string substr(int pos="0," n="npos);//删除pos开始的n个字符，返回修改后的字符串string类的迭代器处理：string类提供了向前和向后遍历的迭代器iterator，迭代器提供了访问各个字符的语法，类似于指针操作，迭代器不检查范围。用string::iterator或string::const_iterator声明迭代器变量，const_iterator不允许改变迭代的内容。常用迭代器函数有：const_iterator" const; 返回pos开始的n个字符组成的字符串string的交换：void swap(string &s2); 交换当前字符串与s2的值string类的查找函数：int find(char c, int 从pos开始查找字符c在当前字符串的位置int find(const char *s, 从pos开始查找字符串s在当前串中的位置int pos, n) 从pos开始查找字符串s中前n个字符在当前串中的位置int string &s, 从pos开始查找字符串s在当前串中的位置 查找成功时返回所在位置，失败返回string::npos的值int rfind(char 从pos开始从后向前查找字符c在当前串中的位置int rfind(const const;int &s,int 从pos开始从后向前查找字符串s中前n个字符组成的字符串在当前串中的位置，成功返回所在位置，失败时返回string::npos的值int find_first_of(char 从pos开始查找字符c第一次出现的位置int find_first_of(const 从pos开始查找当前串中第一个在s的前n个字符组成的数组里的字符的位置。查找失败返回string::nposint find_first_not_of(char find_first_not_of(const pos,int 从当前串中查找第一个不在串s中的字符出现的位置，失败返回string::nposint find_last_of(char find_last_of(const find_last_not_of(char find_last_not_of(const find_last_of和find_last_not_of与find_first_of和find_first_not_of相似，只不过是从后向前查找string类的替换函数：string &replace(int p0, n0,const *s); 删除从p0开始的n0个字符，然后在p0处插入串sstring n); 删除p0开始的n0个字符，然后在p0处插入字符串s的前n个字符string &s); 删除p0开始的n0个字符，然后在p0处插入串s中从pos开始的n个字符string n0,int n, c); 删除p0开始的n0个字符，然后在p0处插入n个字符cstring &replace(iterator first0, iterator last0,const 把[first0，last0）之间的部分替换为字符串sstring 把[first0，last0）之间的部分替换为s的前n个字符string 把[first0，last0）之间的部分替换为串sstring last0,int 把[first0，last0）之间的部分替换为n个字符cstring last0,const_iterator first, const_iterator last); 把[first0，last0）之间的部分替换成[first，last）之间的字符串string类的插入函数：string &insert(int const *s);string n);string p0,const &s);string 前4个函数在p0位置插入字符串s中pos开始的前n个字符string 此函数在p0处插入n个字符citerator insert(iterator it, 在it处插入字符c，返回插入后迭代器的位置void 在it处插入[first，last）之间的字符void 在it处插入n个字符cstring类的删除函数iterator erase(iterator 删除[first，last）之间的所有字符，返回删除后迭代器的位置iterator it); 删除it指向的字符，返回删除后迭代器的位置string &erase(int begin()const;iterator begin(); 返回string的起始位置const_iterator end()const;iterator end(); 返回string的最后一个字符后面的位置const_iterator rbegin()const;iterator rbegin(); 返回string的最后一个字符的位置const_iterator rend()const;iterator rend(); 返回string第一个字符位置的前面rbegin和rend用于从后向前的迭代访问，通过设置迭代器string::reverse_iterator,string::const_reverse_iterator实现字符串流处理：通过定义ostringstream和istringstream变量实现，头文件中例如： string input("hello,this is a test"); istringstream is(input); string s1,s2,s3,s4; is>>s1>>s2>>s3>>s4;//s1="hello,this",s2="is",s3="a",s4="test" ostringstream os; os< < < <
6.stable_sort
sort优点一大堆，一个缺点就是它不是一种稳定的排序。要追求稳定性，只好用stable_sort了。
在各种排序算法中，合并排序是稳定的，但一般的合并排序需要额外的O(N)的存储空间，而这个条件不是一定能够满足的。所以在stable_sort内部，首先判断是否有足够的额外空间，有的话就使用普通合并函数，总的时间复杂性和快速排序一个数量级，都是O(N*logN)。
如果没有额外空间，使用了一个merge_without_buffer的关键函数进行就地合并，这个合并过程不需要额外的存储空间（递归的堆栈除外），但时间复杂度变成O(N*logN)，这种情况下，总的stable_sort时间复杂度是O(N*logN*logN)。