2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) D 二分

2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) D

考虑一条长长的走廊，它可以被分成大小为 1×1 的 n  个正方形单元格。这些单元格从左到右依次编号为 1 至 n 。

走廊上有两个人，一个小流氓和一个保安。一开始，流氓在 ath单元，保安在 bth单元( a≠b )。

 其中一种可能的情况。走廊由 77 个牢房组成，流氓在 33 个牢房里，保安在 66 个牢房里( n=7 , a=3 , b=6 )。

流氓的口袋里有 m 个鞭炮， i 个鞭炮在点燃后的 si 秒内爆炸。

以下事件每秒都会发生(按顺序，完全按以下顺序)：

1. 首先，流氓要么移动到相邻的牢房(从 i 号牢房，他可以移动到 (i+1) 号牢房或 (i−1) 号牢房，并且不能离开走廊)，要么留在当前牢房。如果流氓不移动，他可以点燃**个鞭炮并扔掉。流氓不能进入守卫所在的牢房； 其次，一些已经扔下的鞭炮可能会爆炸。从形式上来说，如果 j 的鞭炮是在 Tth秒扔下的，那么它就会在 (T+sj)th秒爆炸(例如，如果 sj=2 的鞭炮是在 4th秒扔下的，那么它就会在 6th秒爆炸)；
2. 最后，警卫移动一个牢房靠近流氓。如果警卫移动到流氓所在的牢房，流氓就会被抓住。

显然，流氓迟早会被抓住，因为走廊是有限的。他的目标是在被抓之前看到最大数量的鞭炮爆炸；也就是说，他的行动是为了在被抓之前看到最大数量的鞭炮爆炸。

你的任务是计算出如果流氓的行为是最优的，那么这种鞭炮的数量是多少。

输入

第一行包含一个整数 t ( 1≤t≤1000 ) - 测试用例的数量。

每个测试用例由两行组成。第一行包含四个整数 n 、 m 、 a 和 b ( 2≤n≤109 ； 1≤m≤2⋅105 ； 1≤a,b≤n ； a≠b )。( 2≤n≤109 ; 1≤m≤2⋅105 ; 1≤a,b≤n ; a≠b )--分别是走廊的大小、鞭炮的数量、流氓的初始位置和警卫的初始位置。

第二行包含 m 个整数 s1 、 s2 、......、 sm( 1≤si≤109 )。( 1≤si≤109 )，其中 si�� 是 i� 个鞭炮点燃后爆炸所需的时间。

保证所有测试用例的 m 之和不超过 2⋅105 。

输出

对于每个测试用例，打印一个整数--流氓在被抓之前最多可以引爆的鞭炮数量。

注

在第一个测试案例中，流氓的行为举例如下：

• 第二步 1：放下第二个鞭炮，让它在 5th 秒爆炸。警卫移动到 5 格；
• 第二个 2：移动到 2 格。守卫移动到 4 格；
• 第二个 3: 扔下第一个鞭炮，让它在第 4 秒爆炸。守卫移动到 3 格；
• 第二个 4: 移动到 1 格。第一个鞭炮爆炸。守卫移动到 2 格；
• 第二个 5：留在 1 格。第二个鞭炮爆炸。守卫移动到 1 牢房，抓住流氓。

 思想

首先将炸弹爆炸时间从小到达排序,因为肯定优先选择爆炸时间快的.

如果x个炸弹可以成功,那么x-1个也一定能成功,满足单调性,因此可以二分.

二分炸弹要引爆的数量mid,那么肯定是选择e[1,mid],因为前mid个爆炸时间最短,
同时,在点燃和逃跑过程中,容易想到一定是先点燃完这mid个炸弹,
然后将剩下的时间全部用来逃跑拖时间,
因此check就是判断点燃+跑的过程中是否会被抓到.

一个小细节是:
因为我们目标是点燃这mid个炸弹,那么我们一定是先点燃e[mid],然后点燃e[mid-1],最后e[1],
因为跑的过程中炸弹也会计时,逆序点燃才能使得所有炸弹爆炸的总时间最少.
 

代码

// Problem: D. Firecrackers
// Contest: Codeforces - 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
// URL: https://codeforces.com/contest/1468/problem/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 2e6+5;int n,m,a,b;
int t[N];bool check(int mid){int x=a,y=b;int baozha=0;for(int i=mid;i>=1;i--){if(y>x) y--;else y++;baozha--;baozha=max(baozha,t[i]);if(x==y) return 0;}int pao=0;if(x<y) pao=y-1;else pao=n-y;return baozha<=pao;
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T;cin>>T;while(T--){cin>>n>>m>>a>>b;for(int i=1;i<=m;i++){cin>>t[i];}sort(t+1,t+m+1);int res=0;int l=1,r=m;while(l<=r){int mid=(l+r)/2;if(check(mid)){res=mid;l=mid+1;}else r=mid-1;}cout<<res<<"\n";}return 0;	}