Lamps(STL+双端队列)

 Lamps

题面翻译

有 $n$ 盏灯，每盏灯有不亮，亮，坏掉 3 种状态。一开始每盏灯都不亮。

第 $i$ 盏灯有属性 $a_i,b_i$。每次操作你可以选择一盏灭的灯将其点亮，并得到 $b_i$ 的分数。

每次操作结束后，记有 $x$ 盏灯亮着，则所有 $a_i \le x$ 的灯 $i$ 都会损坏（无论是否亮着）。

求能得到的最大分数。多组数据。

题目描述

You have $ n $ lamps, numbered by integers from $ 1 $ to $ n $ . Each lamp $ i $ has two integer parameters $ a_i $ and $ b_i $ .

At each moment each lamp is in one of three states: it may be turned on, turned off, or broken.

Initially all lamps are turned off. In one operation you can select one lamp that is turned off and turn it on (you can't turn on broken lamps). You receive $ b_i $ points for turning lamp $ i $ on. The following happens after each performed operation:

- Let's denote the number of lamps that are turned on as $ x $ (broken lamps do not count). All lamps $ i $ such that $ a_i \le x $ simultaneously break, whether they were turned on or off.

Please note that broken lamps never count as turned on and that after a turned on lamp breaks, you still keep points received for turning it on.

You can perform an arbitrary number of operations.

Find the maximum number of points you can get.

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of lamps.

Each of the next $ n $ lines contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i \le n, 1 \le b_i \le 10^9 $ ) — parameters of the $ i $ -th lamp.

It is guaranteed that sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

 输出格式

For each test case, output one integer — the maximum number of points you can get.

样例 #1

样例输入 #1

```
4
4
2 2
1 6
1 10
1 13
5
3 4
3 1
2 5
3 2
3 3
6
1 2
3 4
1 4
3 4
3 5
2 3
1
1 1
```

样例输出 #1

```
15
14
20
1
```

提示

In first test case $ n = 4 $ . One of ways to get the maximum number of points is as follows:

- You turn lamp $ 4 $ on and receive $ b_4 = 13 $ points.
- The number of lamps that are turned on is $ 1 $ , so all lamps with $ a_i \le 1 $ (namely lamps $ 2 $ , $ 3 $ and $ 4 $ ) break. Lamp $ 4 $ is no longer turned on, so the number of lamps that are turned becomes $ 0 $ .
- The only lamp you can turn on is lamp $ 1 $ , as all other lamps are broken. You receive $ b_1 = 2 $ points for turning it on.
- The number of lamps that are turned on is $ 1 $ . As $ a_1 = 2 $ , lamp $ 1 $ doesn't break.

Your receive $ 13 + 2 = 15 $ points in total. It can be shown that this is the maximum number of points you can get, so the answer for the first test case is $ 15 $ .

In the second test case, one of the ways to get the maximum number of points is as follows:

- On the first operation you turn on lamp $ 4 $ and receive $ 2 $ points. No lamps break after the first operation.
- On the second operation you turn on lamp $ 3 $ and receive $ 5 $ points. After the second operation, there are $ 2 $ lamps turned on. As $ a_3 \le 2 $ , lamp $ 3 $ breaks.
- On the third operation, you turn on lamp $ 1 $ and receive $ 4 $ points.
- On the fourth operation, you turn on lamp $ 5 $ and receive $ 3 $ points. After that there are $ 3 $ lamps turned on: lamps $ 1 $ , $ 4 $ and $ 5 $ . Lamps $ 1 $ , $ 2 $ , $ 4 $ and $ 5 $ simultaneously break, because for all of them $ a_i \le 3 $ .

You receive $ 2 + 5 + 4 + 3 = 14 $ points in total. It can be shown that this is the maximum number of points you can get.

In the third test case, one of the ways to get the maximum number of points is as follows:

- Turn the lamp $ 3 $ on and receive $ 4 $ points. Lamps $ 1 $ and $ 3 $ break.
- Turn the lamp $ 2 $ on and receive $ 4 $ points.
- Turn the lamp $ 6 $ on and receive $ 3 $ points. Lamp $ 6 $ breaks.
- Turn the lamp $ 4 $ on and receive $ 4 $ points.
- Turn the lamp $ 5 $ on and receive $ 5 $ points. Lamps $ 2 $ , $ 4 $ and $ 5 $ break.

You receive $ 4 + 4 + 3 + 4 + 5 = 20 $ points in total. It can be shown that this is the maximum number of points you can get.

// 代码实现能力太差!不会灵活运用stl
// 本题思路很明确,是贪心,设给出的灯中a最大的是x
// 假设x为3,那么只需要,a=1的取一个最大的,a=2的取两个最大的,a=3的取3个最大的即可
// 这段代码实现起来对我来说很难
//所以我找到了两种方法:

//第一种:map+set+vector
//先利用vector+pair存储数据,然后分组,先把所有的a利用set排序,然后利用map将a与所有的b一一对应
//一个a对应多个b,然后排序
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
bool cmp(int aa,int bb){
    return aa>bb;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        vector<pair<int,int>>g(n);
        res=0,num=0,ans=-0x3f3f3f;
        for(int i=0;i<n;i++) cin>>g[i].first>>g[i].second;
        map<int,vector<int>>mp;
        set<int>p;
        for(int i=0;i<n;i++){
            p.insert(g[i].first);
            mp[g[i].first].push_back(g[i].second);
        }
        for(auto i:p) sort(mp[i].begin(),mp[i].end(),cmp);
        for(auto i:mp){
            for(int j=0;j<min((int)i.first,(int)i.second.size());j++) res+=i.second[j];
        }
        cout<<res<<endl;
    }
    return 0;
}

//第二,双端队列,也是利用pair数组,然后定义一个双端队列
//按规则排序之后,用s记录灯的数量,也就是队列的长度,num用来记录现在什么样的a能放
//只要当前的a大于num的时候,这个灯能放,然后就放进去
//记录q数组的长度,看看队列里面有没有被踢出去的灯
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,f[N],res,num,ans,m;
bool cmp(pair<int,int> a,pair<int,int>b)
{
    if(a.first==b.first) return a.second>b.second;
    else return a.first<b.first;   
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        res=0,num=0;
        cin>>n;
        pair<int,int>g[N];
        deque<pair<int,int>>q;
        for(int i=0;i<n;i++) cin>>g[i].first>>g[i].second;
        sort(g,g+n,cmp);
        for(int i=0;i<n;i++){
            if(g[i].first<=num) continue;
            q.push_back(g[i]);
            res+=g[i].second;
            int s=q.size();
            num=max(num,s);
            while(q.size()&&q.front().first<=s) q.pop_front();
        }
        cout<<res<<endl;
    }
    return 0;
}