首页 > 代码库 > HDU 4022 stl multiset
HDU 4022 stl multiset
orz kss太腻害了。
一、set和multiset基础
set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是后者允许元素重复而前者不允许。
需要包含头文件：
#include <set>
set和multiset都是定义在std空间里的类模板：
二、set和multiset的功能
和所有关联式容器类似，通常使用平衡二叉树完成。事实上，set和multiset通常以红黑树实作而成。
自动排序的优点是使得搜寻元素时具有良好的性能，具有对数时间复杂度。但是造成的一个缺点就是：
不能直接改变元素值。因为这样会打乱原有的顺序。
改变元素值的方法是：先删除旧元素，再插入新元素。
存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。
详见：http://blog.csdn.net/xiajun07061225/article/details/7459206
Bombing
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 2608 Accepted Submission(s): 978
Problem Description
It’s a cruel war which killed millions of people and ruined series of cities. In order to stop it, let’s bomb the opponent’s base. It seems not to be a hard work in circumstances of street battles, however, you’ll be encountered a much more difficult instance: recounting exploits of the military. In the bombing action, the commander will dispatch a group of bombers with weapons having the huge destructive power to destroy all the targets in a line. Thanks to the outstanding work of our spy, the positions of all opponents’ bases had been detected and marked on the map, consequently, the bombing plan will be sent to you. Specifically, the map is expressed as a 2D-plane with some positions of enemy’s bases marked on. The bombers are dispatched orderly and each of them will bomb a vertical or horizontal line on the map. Then your commanded wants you to report that how many bases will be destroyed by each bomber. Notice that a ruined base will not be taken into account when calculating the exploits of later bombers.
Input
Multiple test cases and each test cases starts with two non-negative integer N (N<=100,000) and M (M<=100,000) denoting the number of target bases and the number of scheduled bombers respectively. In the following N line, there is a pair of integers x and y separated by single space indicating the coordinate of position of each opponent’s base. The following M lines describe the bombers, each of them contains two integers c and d where c is 0 or 1 and d is an integer with absolute value no more than 109, if c = 0, then this bomber will bomb the line x = d, otherwise y = d. The input will end when N = M = 0 and the number of test cases is no more than 50.
Output
For each test case, output M lines, the ith line contains a single integer denoting the number of bases that were destroyed by the corresponding bomber in the input. Output a blank line after each test case.
Sample Input
3 2 1 2 1 3 2 3 0 1 1 3 0 0
Sample Output
2 1
Source
The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest
Recommend
lcy
代码来自kss，自己的不好意思贴了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<map> 5 #include<set> 6 using namespace std; 7 int n,m; 8 map<int,multiset<int> >mp1,mp2; //mp1以x为键值,mp2以y为键值 9 multiset<int>::iterator it;10 int main()11 {12 //freopen("text.txt","r",stdin);13 while(~scanf("%d%d",&n,&m) && n+m){14 int x,y,d;15 mp1.clear(); mp2.clear();16 for(int i=0;i<n;i++){17 scanf("%d%d",&x,&y);18 mp1[x].insert(y);19 mp2[y].insert(x);20 }21 for(int i=0;i<m;i++){22 int cnt=0;23 scanf("%d%d",&d,&x);24 if(d == 0){25 cnt=mp1[x].size();26 for(it=mp1[x].begin();it!=mp1[x].end();it++)27 mp2[*it].erase(x);28 mp1[x].clear();29 }30 else {31 cnt=mp2[x].size();32 for(it=mp2[x].begin();it!=mp2[x].end();it++)33 mp1[*it].erase(x);34 mp2[x].clear();35 }36 printf("%d\n",cnt);37 }38 printf("\n");39 }40 return 0;41 }
HDU 4022 stl multiset
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。