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

UVA 11020 - Efficient Solutions(set)

UVA 11020 - Efficient Solutions

题目链接

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

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

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;

int t, n;
struct Point {
    int x, y;
    bool operator < (const Point &c) const {
	if (x == c.x) return y < c.y;
	return x < c.x;
    }
};

multiset<Point> s;
multiset<Point>::iterator it;

int main() {
    int cas = 0;
    cin >> t;
    while (t--) {
	s.clear();
	cin >> n;
	Point u;
	cout << "Case #" << ++cas << ":" << endl;
	while (n--) {
	    cin >> u.x >> u.y;
	    it = s.lower_bound(u);
	    if (it == s.begin() || (--it)->y > u.y) {
		s.insert(u);
		it = s.upper_bound(u);
		while (it != s.end() && it->y >= u.y) s.erase(it++);
	    }
	    cout << s.size() << endl;
	}
	if (t) cout << endl;
    }
    return 0;
}


UVA 11020 - Efficient Solutions(set)