結構體如何用multiset
c++語言中,multiset是<set>庫中一個非常有用的類型,它可以看成一個序列,插入一個數,删除一個數都能夠在O(logn)的時間内完成,而且他能時刻保證序列中的數是有序的,而且序列中可以存在重複的數。
自定義類型的資料呢?
不隻是int類型,multiset還可以存儲其他的類型諸如 string類型,結構(struct或class)類型。而我們一般在程式設計當中遇到的問題經常用到自定義的類型,即struct或class。例如下面的例子:
struct rec{
int x,y;
};
multiset<rec> s;
不過以上的代碼是沒有任何用處的,因為multiset并不知道如何去比較一個自定義的類型。怎麼辦呢?我們可以定義multiset裡面rec類型變量之間的小于關系的含義(這裡以x為第一關鍵字為例),具體過程如下:
定義一個比較類cmp,cmp内部的operator函數的作用是比較rec類型a和b的大小(以x為第一關鍵字,y為第二關鍵字):
struct rec {
int x,y;
bool operator<( const node&b )const {
if ( x==b.x ) return y<b.y;
return x>b.x;
}
};
multiset<rec> s;
常用知識點:
1. 得到最小值 ------ *s.begin() .
2. 得到最大值 ------ *s.rbegin() .
3. 删除某個值 ------ s.erase(s.find(x)) .
4. 删除最大值 ------s.erase(s.find(*s.rbegin())) .
5. 二分查找 ------*s.lower_bound( value ) .
例題1:https://vjudge.net/problem/Kattis-gcpc
題意:n個隊伍,m條實時消息( i, p )。表示第 i 個隊伍成功AC一道題,增加罰時 p. 輸出m行,表示每條實時消息後1号隊伍的排名。按照AC題數,罰時,隊伍編号,來進行排名。
思路:考慮用multiset來存排行榜并進行維護。全存的話就T4了,是以不能全存,我們手動優化後隻存比1号隊伍排名靠前的,其他的在結構體裡暫時存放。
Sample Input 1 | Sample Output 1 |
---|---|
| |
代碼:
#include <bits/stdc++.h>
using namespace std;
struct node {
int x,y,id;
bool operator<( const node&b )const {
if ( x==b.x && x==0 ) return id<b.id;
if ( x==b.x ) return y<b.y;
return x>b.x;
}
};
multiset<node> s;
node a[200005];
int n,m;
int main()
{
cin >> n >> m;
for ( int i=1; i<=n; i++ ) {
a[i].x=0; a[i].y=0; a[i].id=i;
s.insert(a[i]);
}
for ( int i=0; i<m; i++ ) {
int u,v;scanf("%d %d",&u,&v);
if ( a[u]<a[1] ) s.erase(s.find(a[u]));
a[u].x = a[u].x+1;
a[u].y += v;
s.insert(a[u]);
while ( s.size()>0 && !(*s.rbegin()<a[1]) ) s.erase(s.find(*s.rbegin()));
printf("%d\n",s.size()+1);
}
return 0;
}