C. Keshi Is Throwing a Party
题意:
有n个人,你要从中选出k个满足条件的人,让k最大化。
对于第i个人,他希望选出来的人中,在他后面不能超过a[i]人,在他前面不能超过b[i]人。
做法:
条件中的a[i]具有后效性,所以不可以dp解决,(无论是正着dp还是倒着,都不能解决这个后效性)。考虑到最后的答案具有单调性,所以可以二分答案。
考虑一个集合,里面有x个人了,他们是符合条件的,如果想要添加一个人进入这个集合,然后毫不影响前面的人:
-
对于条件b,这个很容易想到,只要b[i] - x >= 0即可。
-
对于条件a,想要毫不影响前面的人,不如考虑当这个人加入集合后,绝对不影响后面的人加入。那就和当前枚举的mid有关了,他后面还有mid - x - 1个人,那么a[i] - (mid - x - 1) >= 0,这个人才可以加入。
最后判断x是不是大于等于mid,就能知道合不合法了。
int a[N], b[N];
int n;
bool check(int mid)
{
int ret = 0;
for (int i = 1; i <= n; i++){
if (a[i] - (mid - ret - 1) >= 0 && b[i] - ret >= 0) ret++;
}
return ret >= mid;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i] >> b[i];
}
int l = 1, r = n;
while(l < r){
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << "\n";
}