自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:52:42，当前版本为作者最后更新于2024-02-23 22:54:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑二分答案 $t$，求出在 $t$ 个时刻内最多能有多少只蚂蚁。

对于一个洞口，一定是先放出一些蚂蚁，再接进一些蚂蚁。

可以发现，对于第 $i$ 个洞口，出去的第 $j$ 只蚂蚁到达冰箱的时间是 $a_i+j$，接进来的倒数第 $j$ 只蚂蚁要在 $t-j-a_i$ 时刻前到达冰箱。

假如我们已经知道每个洞口出去和进来了多少只蚂蚁，那么就变成了一个二分图匹配问题。

因为每个洞口出去和进来的蚂蚁本质是相同的，所以我们会让前一半的时间出蚂蚁，后一半的时间进蚂蚁。

那么在 $t$ 是奇数的时候中间的时刻不好决定，因此我们改成每个时刻可以进去或出来 $2$ 只蚂蚁，中间时刻 $1$ 进 $1$ 出，最后答案除以 $2$。

直接做二分图匹配是不行的，但发现每个左部点连接的都是右部的一个后缀，因此从前到后扫 $t$ 个时刻，每次直接贪心的匹配所有可以匹配的右部点。

这样每次是 $O(t)$ 的，但注意到每个时刻新加入的左部点数量和右部点数量的变化次数是 $O(n)$ 的，于是可以离散化后对于数量相同的一起处理。

时间复杂度 $O(n\log n\log V)$，常数较大，但因为有 $8s$ 的时限可以通过。

注意到每个函数的形状是相同的，所以可以提前将 $a_i$ 排好序后归并几种端点，时间复杂度 $O(n(\log n+\log V))$。

这里只实现了 $O(n\log n\log V)$ 的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int T,n,a[N],cp;
ll m;
struct opt{
	ll x;int t,c;
	bool operator <(const opt b)const{return x<b.x;}
}p[N*6];
bool check(ll t){
	cp=0;
	ll h=t>>1;
	for(int i=1;i<=n;++i){
		if(t&1){
			p[++cp]={a[i]+1,0,2};
			p[++cp]={a[i]+h+1,0,-1};
			p[++cp]={a[i]+h+2,0,-1};
			p[++cp]={h-a[i],1,1};
			p[++cp]={h-a[i]+1,1,1};
			p[++cp]={t-a[i],1,-2};
		}else{
			p[++cp]={a[i]+1,0,2};
			p[++cp]={a[i]+h+1,0,-2};
			p[++cp]={h-a[i],1,2};
			p[++cp]={t-a[i],1,-2};
		}
	}
	ll sf=0,st=0,res=0,rs=0;
	sort(p+1,p+cp+1);
	for(int i=1;i<cp;++i){
		if(!p[i].t)sf+=p[i].c;
		else st+=p[i].c;
		ll dt=p[i+1].x-p[i].x;
		if(!dt)continue;
		if(sf>=st)res+=st*dt,rs+=(sf-st)*dt;
		else{
			rs+=sf*dt;
			ll u=min(st*dt,rs);
			rs-=u,res+=u;
		}
	}
	return res>=m*2;
}
void solve(){
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	ll l=2*m/n,r=2.1e14;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}