Codeforces 1612C. Keshi Is Throwing a Party

思路

首先容易发现,选择的人数具有单调性,是可以二分的

假设最后答案选了 $x$ 个人,那么对于一个人有影响的,就只有了他前面选了多少人,因为前面确定了后面就确定了

更具体地说,如果第 $i$ 个人是按顺序的第 $k$ 个被选,那么 $x-k\le a_i$ 且 $k\le b_i$ 综合一下可以得到 $x-a_i\le k\le b_i$

这个不等式实际上说明了一种贪心的正确性,顺序遍历,能选就选

因为确定 $x$ 之后,能否选择仅与 $k$ 有关,所以尽量在更小的范围内选更多的人肯定不会更劣

代码

#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
#define ls (loc<<1)
#define rs ((loc<<1)|1)
const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;
int n;
int a[200200], b[200200];
bool check(cint x) {
int r = 0;
for(int i=1; i<=n; i++)
if(b[i] >= r && a[i] >= x - r - 1) ++ r;
return r >= x;
}
int main() {
//freopen("1.in", "r", stdin);
//cout.flags(ios::fixed); cout.precision(8);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T_=1;
std::cin >> T_;
for(int _T=1; _T<=T_; _T++) {
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i] >> b[i];
int l = 1, r = n, mid;
while(l < r) {
mid = l + (r - l + 1) / 2;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
return 0;
}

题外话()

没想到糖糖子明从8分过B开始就被这题卡了3h

实际上,赛中第一眼就是二分,然而草草想过之后发现不知道怎么验证(也就是没看见贪心)

然后就去推结论,还真的推出来一些看上去挺真的,最后竟然归结为求带修第 $k$ 小 ()

愤而找了平衡树板子,然后wa2

赛时我是这么想的

考虑当前要加入一个点,有三种冲突情况

如果仅是前面的点导致的冲突(即前面有一个 $a_i$ 过小),那么就删掉最小的 $a_i$ 中最靠右的那一个

如果仅是当前的点 $b_i$ 过小,那么将当前选择的点的 $a_i$ 第 $size-b_i$ 小的点删除,加入此点,意义为如果 $1$ 到 $size-b_i-1$ 都被删掉了,那么我可以反悔选上这个点,如果没被删掉也不会影响答案

如果都冲突了,就先考虑第一个,然后考虑第二个

隔了一天,仔细一想,错的离谱,主要是删掉一个点会影响到部分点的 $a_i$ ,有一部分又不会被影响…g

如果哪位大佬有继续往下的思路可以给这位萌新讲解一下,o(╥﹏╥)o

最后

以上就是漂亮服饰为你收集整理的Codeforces 1612C. Keshi Is Throwing a PartyCodeforces 1612C. Keshi Is Throwing a Party的全部内容，希望文章能够帮你解决Codeforces 1612C. Keshi Is Throwing a PartyCodeforces 1612C. Keshi Is Throwing a Party所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。