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;

}