CF1866G Grouped Carriages

, ,

Descritpion

https://www.luogu.com.cn/problem/CF1866G

Solution

最大值的最小值考虑二分。

如果考虑直接贪心的话，有可能向左也有可能向右感觉很不好处理。

对于第 $i$ 个车厢的人，可以转化为任意在 $[i-d_i,i+d_i]$ 车厢内活动。避免向左向右，可以理解为在 $i-d_i$ 的位置，可以向右边的距离为 $2d_i$。

这样就很好做了嘛！拿个小根堆维护右端点即可。

复杂度 $O(n\log w\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define int long long 
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename ...S>
Tp void read(T &x) {
	x=0;int f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x*=f;
}
namespace Debug {
	Tp void _debug(char *f,T x) {cerr<<f<<'='<<x<<endl;}
	Ts void _debug(char *f,T x,S... t) {while (*f!=',') cerr<<*f++;cerr<<'='<<x<<',';_debug(f+1,t...);}
	#define gdb(...) _debug((char *)#__VA_ARGS__,__VA_ARGS__)
}
using namespace Debug ;
#define fi first
#define se second
#define mk make_pair
int n,a[maxn],d[maxn],c[maxn];
vector<pair<int,int> >O[maxn];
bool check(int val) {
	int i;
	priority_queue<pair<int,int> >q;
	while (!q.empty()) q.pop();
	for (i=1;i<=n;i++) a[i]=c[i];
	for (i=1;i<=n;i++) {
		for (auto tmp:O[i]) q.push(mk(-tmp.fi,tmp.se));
		int sum=0;
		while (!q.empty()) {
			auto tmp=q.top();q.pop();
			if (-tmp.fi<i) return 0;
			if (tmp.se+sum>val) {q.push(mk(tmp.fi,tmp.se-(val-sum)));break;}
			else sum+=tmp.se;
		}
	}
	return q.empty()==1;
}
signed main(void) {
	int i,sum=0;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),c[i]=a[i],sum+=a[i];
	for (i=1;i<=n;i++) read(d[i]),O[max(i-d[i],1ll)].push_back(mk(i+d[i],a[i]));
	int l=(sum+n-1)/n-1,r=sum,mid;
	while (l+1<r) {
		mid=l+r>>1;
		if (check(mid)) r=mid;
		else l=mid;
//		gdb(l,r);
	}
	printf("%d",r);
	return 0;
}