【UOJ#49】【UR #3】轴仓库

题面

UOJ

题解

不难发现一定是每次找到离当前位置最近的一个箱子，然后把它搬过来。

那么如果我们能够确定起始位置，我们就可以二分从两侧多少距离搬箱子，判断一下时间就好了。

考虑起始位置，发现一定可以让起始位置有箱子，因为这东西本质上就是一个中位数的模型。

考虑二分答案，于是我们要求的就变成了取\(mid\)个箱子所需的最短时间。

因为取走的箱子在数轴上一定是连续的一段，我们考虑从左往右枚举一个\(s\)，那么当且仅当\(r+1\)比\(l\)更远时才不会进行替换，否则选择\(r+1\)一定比选择\(l\)更优。此时\(l,r\)单增，直接在扫的过程中维护一下就好了。

然而上面这种方法需要把所有的\(a_i\)变成若干个\(1\)来考虑，所以复杂度是\(O(\log n(n+\sum a_i))\)。

而实际上这个过程可以省略掉大量重复操作，即只需要记录一下重复位置的选择个数就好了。

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

#define MAX 500500

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,x[MAX],a[MAX];

ll s1[MAX],s2[MAX],T;

bool check(ll mid)

{

	int l=1,r=lower_bound(&s1[1],&s1[n+1],mid)-s1,L=a[1],R=mid-s1[r-1];

	for(int i=1;i<=n;++i)

	{

		while(l<i&&r<=n)

		{

			ll v1=x[i]-x[l],v2=x[r]-x[i];

			if(v1>v2)

			{

				int cnt=min(L,a[r]-R);

				L-=cnt;R+=cnt;

				if(!L)++l,L=a[l];

				if(R==a[r])++r,R=0;

			}

			else break;

		}

		ll ret=(s1[i]-s1[l])*x[i]-(s2[i]-s2[l])+1ll*L*(x[i]-x[l])+(s2[r-1]-s2[i])-(s1[r-1]-s1[i])*x[i]+1ll*R*(x[r]-x[i]);

		if(ret*2<=T)return true;

	}

	return false;

}

int main()

{

	n=read();T=read();

	for(int i=1;i<=n;++i)x[i]=read();

	for(int i=1;i<=n;++i)a[i]=read(),s1[i]=s1[i-1]+a[i],s2[i]=s2[i-1]+1ll*a[i]*x[i];

	ll l=0,r=s1[n],ret=0;

	while(l<=r)

	{

		ll mid=(l+r)>>1;

		if(check(mid))l=mid+1,ret=mid;

		else r=mid-1;

	}

	printf("%lld\n",ret);

}