题解：CF1866G Grouped Carriages
letianJOE
·
·
题解
思路
二分：
我们能够发现答案具有单调性。
也就是说如果答案 Z=x 能够通过移动满足，则 Z=x+1 也可以通过移动满足。这是显然的。
既然答案具有单调性，我们就可以二分答案。
贪心：
那么现在的问题就变成了如何判断对于一个 Z=x 是否是合法的。
我们考虑对每个车厢进行填充（填充越均匀越好）。
对于第 $i$ 个车厢，若第 $j$ 组乘客可以进入，则需要有 $l_j \le i \le r_j$。
在这些乘客中，贪心的想，我们应该选择 $r_j$ 较小的几组乘客，而且不需要考虑 $l$。
这时为什么呢，我们可以画个图考虑一下。
$a,b$ 是两个车厢，$b>a$。一共有四组乘客 $c_1,c_2,c_3,c_4$，都满足能够移动到 $a$ 车厢。
首先不难发现，有 $l_1,l_2,l_3,l_4<a<b$，这是因为 $l_1,l_2,l_3,l_4<a$，$a<b$。所以在选择那几组乘客移动到 $a$ 时不需要考虑 $l$，因为 $l$ 如果对 $a$ 成立，对 $b$ 也成立。
对于 $r$，我们要选择红色的两个区间，而不是蓝色的区间。因为区间 $2,4$ 无法到达 $b$，如果不选，他们就会堆在 $a$ 上。换句话说，可以理解为他们的时间比较赶，需要早一点分配，不然就分配不上了。
---
### 实现：
大体的贪心其实很好想，我们考虑如何实现，具体是 $check$ 函数怎么选。
首先我们要对乘客按组以 $l$ 为关键字排个序，这样就不需要多花心思处理左端点了。
$r$ 我们每次要选最小的，那就搞一个优先队列，把符合 $l_j \le i$ 的点扔到优先队列中。
然后开始填充车厢。
那么如何判断 $r$ 是否合法呢。从分配的角度想，如果在分配完车厢 $i$ 时，最后还剩下了 $r_j \le i$，也就是说存在一组乘客只能被放到前 $i$ 个车厢中，但是这几个车厢已经被填满了，不可能再塞下一组乘客。那么这个 $Z=x$ 就不合法。
---
## 代码
:::info[代码]
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5;
int n;
int maxx;
struct node
{
int l,r,a;
bool operator <(const node &x)const{return r>x.r;}
}carriage[N+5];
bool cmp(node x,node y){return x.l<y.l;}
bool check(int k)
{
priority_queue<node>que;
int left=1;
for(int i=1;i<=n;i++)
{
while(left<=n && carriage[left].l<=i)
{
que.push(carriage[left]);
left++;
}
int need=k;
while(need && que.size())
{
node x=que.top();
que.pop();
if(need>x.a) need-=x.a;
else
{
x.a-=need;
need=0;
que.push(x);
}
}
while(que.size() && !que.top().a) que.pop();
if(que.size() && que.top().r<=i) return false; //判断不合法
}
if(que.size()) return false; //没分配完也是不合法
return true;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>carriage[i].a;
for(int i=1;i<=n;i++)
{
maxx=max(maxx,carriage[i].a);
int d;
cin>>d;
carriage[i].l=max(i-d,(int)1),carriage[i].r=min(i+d,n);
}
sort(carriage+1,carriage+n+1,cmp);
int l=-1,r=maxx+1;
while(l+1<r) //二分答案
{
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
cout<<r<<"\n";
return 0;
}
```
:::