hdu4022 map+multiset
2023-09-11 14:13:59 时间
题意:
给你一些敌人的坐标,每次让你删除某一行或者某一列,问你每一次操作能删除多少人.....
思路:
给你一些敌人的坐标,每次让你删除某一行或者某一列,问你每一次操作能删除多少人.....
思路:
map和multiset的完美结合,吧set定义到map里,达到一个一对多的效果,其实就是实现一个一维multi数组,可以随时查询长度的数组,同时用map还可以达到离散化的效果,开两个数组,表示 markx[] ,marky[], x所在行 和 y所在列的元素,这样每次 清除一行 和 另一个数组中的某些元素,或者清除一列和另一个数组中的某些元素,达到越删除越快的效果,时间复杂度最大是 O(n).......
#include<stdio.h> #include<map> #include<set> using namespace std; map<int ,multiset<int> >markx ,marky; multiset<int>::iterator iter; int main () { int n ,m ,i ,a ,b; while(~scanf("%d %d" ,&n ,&m) && n + m) { markx.clear(); marky.clear(); for(i = 1 ;i <= n ;i ++) { scanf("%d %d" ,&a ,&b); markx[a].insert(b); marky[b].insert(a); } for(i = 1 ;i <= m ;i ++) { scanf("%d %d" ,&a ,&b); int ans; if(!a) { ans = markx[b].size(); for(iter = markx[b].begin() ;iter != markx[b].end() ;iter ++) { marky[*iter].erase(b); } markx[b].clear(); } else { ans = marky[b].size(); for(iter = marky[b].begin() ;iter != marky[b].end() ;iter ++) { markx[*iter].erase(b); } marky[b].clear(); } printf("%d\n" ,ans); } printf("\n"); } return 0; }
相关文章
- java:Conllection(List,set,get,map,subList)使用
- Map接口,Map.Entry,hashMap类,TreeMap类,WeakHashMap。
- [Functional Programming] Arrow contramap vs map and promap
- [Javascript] Ex: concatAll, map and filter
- 把Map 转化为query string
- react.js map遍历的问题
- list,set,map,数组之间的相互转换详细解析
- 机器学习笔记 - IOU、mAP、ROC、AUC、准确率、召回率、F分数
- go gin框架:QueryMap接收map类型请求参数
- rxjs的map和switchMap在SAP Spartacus中的应用 -将高阶Observable进行flatten操作
- Atitit path query 路径查询语言 数据检索语言 目录 1.1. List map >> spel1 1.2. Html数据 》》Css选择符1 1.3. Json 》map》
- Python语言学习:Python语言学习之函数(定义&调用函数/常用内置函数如filter&map/内嵌函数/闭包/匿名函数如lambda&map)的简介、案例应用之详细攻略
- 9.3.1 map端连接- DistributedCache分布式缓存小数据集
- Map存储容量及内存占用测试
- 387集Go语言核心编程培训视频教材整理 | map(二)
- 字母统计-map
- 原创最新|SCI写作必备(一)绘制YOLOv7论文同款性能对比图-Python:包含多种不同功能风格图表|包括mAP、Params、FPS等对比图表(YOLOv6/YOLOv7同款)
- Gstreamer之gst_buffer_map()用法(十七)