[关闭]
@lychee123 2017-10-02T13:43:56.000000Z 字数 1323 阅读 932

map套set的简单应用(ACPC Headquarters : AASTMT (Stairway to Heaven) )

STL


题意

找出相交区间的重复元素,并按照字典序输出。

输入

输入一个 表示 组测试数据
接下来一行输入一个 表示接下来有 行信息的输入
接下来输入 行,每行包含一个字符串表示比赛名称,比赛时间起点,比赛时间终点,该比赛有 个志愿者,这 个志愿者分别叫什么名字
Contest name C, start date S, end date E, number of required volunteers V, followed by V distinct volunteers' names.
每个名字长度不超过10个字符

样例

Input
2
2
lcpc 3 7 4 fegla compo fouad nicole
scpc 5 11 3 fegla fouad nicole
2
jcpc 8 10 2 fegla hossam
scpc 10 15 3 fegla fouad nicole

Output
3
fegla
fouad
nicole
1
fegla

分析

用一个map套multiset。
multiset里面装一个pair表示区间(s,t)
map里面装入志愿者的名字,此时需要去重。但对于区间是允许重复的,所以用multiset
遍历这些人。此时这些人对应的区间都是排好序的。如果出现区间重合则将人名丢进set里面。
最后输出set里面的元素即可。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. char cname[22];//比赛名
  5. char name[22];//志愿者名字
  6. int st,en;//比赛起始时间
  7. int check(multiset<pair<int,int> > &S)//是否冲突的判断函数
  8. {
  9. auto it=S.begin();//定义两个指针,it表示当前位,itt表示it的后一位。
  10. auto itt=it;
  11. for(itt++;itt!=S.end();it++,itt++)
  12. if(it->second >= itt->first)
  13. return false;
  14. return true;//一定要return到位
  15. }
  16. int main()
  17. {
  18. int t;
  19. scanf("%d",&t);
  20. while(t--)
  21. {
  22. map<string,multiset<pair<int,int> > >mp;
  23. set<string>st1;
  24. int n;
  25. scanf("%d",&n);
  26. for(int i=0;i<n;i++)
  27. {
  28. scanf("%s%d%d",cname,&st,&en);
  29. int num;
  30. scanf("%d",&num);
  31. for(int j=0;j<num;j++)
  32. {
  33. scanf("%s",name);
  34. mp[name].emplace(st,en);
  35. }
  36. }
  37. for(auto &p:mp)//auto p:mp表示指针p遍历mp,取引用就直接遍历值了
  38. {
  39. if(!check(p.second))
  40. st1.emplace(p.first);//emplace插入更快
  41. }
  42. printf("%d\n",st1.size());
  43. for(auto &p:st1)
  44. cout<<p<<endl;
  45. }
  46. return 0;
  47. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注