自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:14:29，当前版本为作者最后更新于2020-06-19 23:06:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题又 tricky 样例又水，写的完全是错的死了几遍才过。

假设我们先让每个人都坐摩托。假设所有人去坐摩托，当前能用魔法改变年龄使每个人尽量能坐摩托的花费，以及用了魔法还是不能够坐摩托的人。

我们发现又从大往小了枚举摩托数量，因为车数量增加，不能够坐摩托的人越来越少。显然的摩托减少，车就增加，所以用双指针枚举即可。

注意要将年龄排序。答案最大是 $10^{10}$，故要开 long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1145141919810ll;
LL n,k,lc,pc,lm,pm,t,d,a[100005];
int main(){
	scanf("%lld %lld %lld %lld %lld %lld %lld %lld",&n,&k,&lc,&pc,&lm,&pm,&t,&d);
	for(LL i=1;i<=n;++i)	scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	LL motorDisabled=0ll,cost=0ll,rest=0ll;
	for(LL i=1;i<=n;++i)
	{
		cost+=max(0ll,min(d,lm-a[i]));
		rest+=max(0ll,min(d,a[i]-lm));
		if(a[i]+d<lm)	++motorDisabled;
	}
	LL ans=INF;
	if(rest>=cost && !motorDisabled)	ans=pm*n+cost*t;
	LL l=1,r=n,bus=0ll;
	while(r-l+1>=k)
	{
		++bus;
		for(LL i=0ll;i<k-1;++i)
		{
			cost-=max(0ll,min(lm-a[i+l],d));
			rest+=min(d,min(a[i+l],lm)-1);
			if(a[i+l]+d<lm)	--motorDisabled;
		}
		cost+=max(0ll,lc-max(lm,a[r]));
		rest+=max(0ll,min(d,a[r]-lc))-max(0ll,min(d,a[r]-lm));
		if(a[r]+d<lc)	break;
		if(rest>=cost && !motorDisabled)	ans=min(ans,pm*(n-bus*k)+bus*pc+cost*t);
		l+=k-1;
		--r;
	}
	if(a[r]+d>=lc)
	{
		++bus;
		for(LL i=0ll;i<r-l;++i)
		{
			cost-=max(0ll,min(lm-a[i+l],d));
			rest+=min(d,min(a[i+l],lm)-1);
			if(a[i+l]+d<lm)	--motorDisabled;
		}
		cost+=max(0ll,lc-max(lm,a[r]));
		rest+=max(0ll,min(d,a[r]-lc))-max(0ll,min(d,a[r]-lm));
		if(rest>=cost && !motorDisabled)	ans=min(ans,bus*pc+cost*t);
	}
	printf("%lld",ans!=INF?ans:-1);
	return 0ll;
}