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

样例输出 #1

分析

当灯笼 $i$ 的 $a_i$ 小于等于目前亮着的灯笼个数 $x$ 的时候, 灯笼 $i$ 就会坏掉, 如果它没被点亮, 那么我们很明显就亏了 $b_i$ 的价值

而且很明显的是, $a_i$ 越小对 $x$ 的要求越高, 越容易浪费, 所以我们的思路就是一定要从小的 $a_i$ 开始点亮, 当 a_i 相同时, 我们要先点 $b_i$ 大的灯笼, 而且当一个灯笼被点亮之后坏掉了, 我们仍能保留价值, 且这个坏掉的灯笼不计入 $x$

具体做法是: 对灯笼依据 $a_i$ 升序排列, 相同情况下 $b_i$ 大的放在前边, 然后我们遍历灯笼, 一个一个点亮, 用队列存储自己点亮的灯笼的 $a_i$, 很明显队列中的 $a_i$ 也是非降序的

因为灯笼肯定是从 $a_i$ 小的开始坏起, 符合队列 先进先出 的性质, 每次遍历我们看看队头元素是否小于等于队列的长度, 然后一直弹出直到队头元素大于队列长度, 注意随着弹出队列长度显然

注意, 灯笼所有满足条件的同时坏掉的, 但是队列弹出长度会减小, 所以我们先要把长度存起来

对于 $a$ 是 3 3 3 3 3 3 3 的情况, 我们在点亮第三个灯笼的时候, 不仅队列中的三个灯笼要坏掉, 其他的 $a=3$ 的灯笼也是要坏掉的, 我们不能只依靠队列的弹出来判断灯笼是否坏掉, 所以我们每次要记录最后一个弹出的元素的 $a$ 是多少, 代表着这个值的 $a$ 的灯笼是要坏掉的, 由于排序后 $a$ 满足非递减, 所以我们只需要判断即将要点亮的灯笼的 $a_i$ 是不是等于 $a$ 即可, 如果是就说明之前坏掉了, 是不能点亮的

!: $a$ 和 $b$ 到了 $10^9$ , 无需多言, 开long long

在判断灯笼坏掉的部分, 因为每个灯笼最多也就进队出队一次, 这里的时间复杂度是 $O(n)$ 的, 不难看出总的时间复杂度是 $O(n)$

代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
struct A
{
	ll a, b;
}c[N];

bool cmp(A p, A q)
{
	if(p.a == q.a) return p.b > q.b;
	else return p.a < q.a;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		queue<ll> q;	//存放已经开了的灯 
		int n; cin >> n;
		for(int i = 1; i <= n; i++)
		{
			cin >> c[i].a >> c[i].b;
		}
		sort(c + 1, c + n + 1, cmp);
		ll ans = 0, tobreak = -1;	//tobreak代表也是要坏的灯笼
		for(int i = 1; i <= n; i++)
		{
			ll sz = q.size(); 
			while(q.size())
			{
				ll tmp = q.front();
				if(tmp > sz) break;
				tobreak = tmp, q.pop();
			}
			if(c[i].a == tobreak) continue;
			ans += c[i].b;
			q.push(c[i].a);
		}
		cout << ans << endl; 
	}
}

JZTXT

CF1839B