题解 P5800 【[SEERC2019]Life Transfer】

· · 题解

这道题又 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;
}