題意:
? ? ? 給你一些敵人的坐標,每次讓你刪除某一行或者某一列,問你每一次操作能刪除多少人.....

思路:

? ? ? 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; }

總結

以上是生活随笔為你收集整理的hdu4022 map+multiset的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。