首页 > 代码库 > UVA 11020 - Efficient Solutions(set)

UVA 11020 - Efficient Solutions(set)

2024-07-19 04:24:39   225人阅读

题意：每个人有两个属性值(x, y)，对于每一个人(x,y)而言，当有另一个人(x‘, y‘),如果他们的属性值满足x‘ < x, y‘ <= y或x‘ <= x, y‘ < y的话，这个人会失去优势，每次添加一个人，并输出当前优势人个数

思路：由于每个人失去优势后，不可能再得到优势，所以失去优势就可以当成删去这些点，这样的话，就可以用一个multiset来维护点集，每次加入一个点，利用lowerbound，upper_bound二分查找旁边点的位置来进行判断和删点

代码：

 

[cpp] view plaincopy
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <iostream>  
  4. #include <set>  
  5. using namespace std;  
  6.   
  7. int t, n;  
  8. struct Point {  
  9.     int x, y;  
  10.     bool operator < (const Point &c) const {  
  11.     if (x == c.x) return y < c.y;  
  12.     return x < c.x;  
  13.     }  
  14. };  
  15.   
  16. multiset<Point> s;  
  17. multiset<Point>::iterator it;  
  18.   
  19. int main() {  
  20.     int cas = 0;  
  21.     cin >> t;  
  22.     while (t--) {  
  23.     s.clear();  
  24.     cin >> n;  
  25.     Point u;  
  26.     cout << "Case #" << ++cas << ":" << endl;  
  27.     while (n--) {  
  28.         cin >> u.x >> u.y;  
  29.         it = s.lower_bound(u);  
  30.         if (it == s.begin() || (--it)->y > u.y) {  
  31.         s.insert(u);  
  32.         it = s.upper_bound(u);  
  33.         while (it != s.end() && it->y >= u.y) s.erase(it++);  
  34.         }  
  35.         cout << s.size() << endl;  
  36.     }  
  37.     if (t) cout << endl;  
  38.     }  
  39.     return 0;  
  40. } 

UVA 11020 - Efficient Solutions(set)


联系
我们