題意：
? ? ? 給你N個人，每個人有兩個權值，x,y對于某一個人，如果不存在某一個人x' y',
x' < x && y' <= y 或者x' <= x && y' < y那么這個人就是優勢人群，對于輸入的這n個人，每輸入一個人的時候就輸出一次當前這個人加入之后的當前優勢人群數量。

思路：
? ? ? 可以在一個二維坐標系上找到規律，所有人都可以映射到二維坐標系上的某一個點，對于任意兩個人不同的人（x,y都相等看成一個人）來說，如果他倆都是優勢人群，那么他倆肯定存在這樣的關系 x < x' && y > y'，這樣就在坐標系上形成了一個遞減的線，還有就是在加人的過程中一定要記住，如果這個人在某一步不屬于優勢人群，那么他以后就不可能再是優勢人群中的了，然后考慮每次增加一個人，有兩種情況，（1）當前這個人不是優勢人群，那么直接不做任何操作，判斷方法比較簡單，可以直接找到"大于等于"他的的第一個數的前一個，如果這個數的y比他小，那么就直接斷定當前這個人不是優勢人群。（2）就是加入當前這個人是優勢人群，那么就直接先把這個人加到multiset中，加入之后可能吧別的人變成非優勢群體，然后我們在找到"大于"當前這個人的第一個人開始，一直往后，如果y是大于等于當前這個人的，那么直接刪除。
**如果a能淘汰b,b能淘汰c，那么a也一定能淘汰c,所以如果直接淘汰b不會影響淘汰c的

提示：
（1） 這里的大于等于只是位置上區分的（排序位置是x小的或者x相等y小的在前面）。
（2） 用multiset（可重集）的原因是可能有多個人x,y同時相等
（3） 如果不懂的話建議在二維坐標上模擬下，還有就是考慮下(1,2)(1,2)(1,2)(1,3)這樣的數據，有利于理解二級排序。
（4）*.lower_bound 大于等于的第一個數
（5）*.upper_bound 大于的第一個數


#include<set>
#include<stdio.h>

using namespace std;

typedef struct NODE
{
? ? int x ,y;
? ? friend bool operator < (NODE a ,NODE b)
? ? {
? ? ? ? return a.x < b.x || a.x == b.x && a.y < b.y;
? ? ? ? //這個地方自己目前有不理解的地方，就是我之前寫的優先隊列的姿勢在結合本體?


? ? ? ? // 應該是應該是return a.x > b.x || a.x == b.x && a.y > b.y;
? ? ? ?//沒有正式的學過C++所以..
? ? }
}NODE;


multiset<NODE>myset;
multiset<NODE>::iterator it;


int main ()
{
? ? int t ,cas = 1 ,i ,x ,y ,n;
? ? NODE now;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? printf("Case #%d:\n" ,cas ++);
? ? ? ? scanf("%d" ,&n);
? ? ? ? myset.clear();
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d" ,&x ,&y);
? ? ? ? ? ? now.x = x ,now.y = y;
? ? ? ? ? ? it = myset.lower_bound(now);
? ? ? ? ? ? if(it == myset.begin() ||(--it)->y > y)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? myset.insert(now);
? ? ? ? ? ? ? ? it = myset.upper_bound(now);
? ? ? ? ? ? ? ? while(it != myset.end() && it -> y >= y)
? ? ? ? ? ? ? ? myset.erase(it++);
? ? ? ? ? ? }
? ? ? ? ? ? printf("%d\n" ,myset.size());
? ? ? ? }
? ? ? ? if(t) printf("\n");
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的UVA11020 优势人群（multiset）的全部內容，希望文章能夠幫你解決所遇到的問題。

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