题解：P11142 [APC001] Ex - Separation

lailai0916 · 2026-08-31 06:11:42 · 题解

题意简述

数轴上有若干工厂，货物会在给定时刻产生。每次运输者都从 A 出发，依次经过各工厂和 B，再返回 A。去程会收走沿途已经产生的全部货物。

运输者可以在一次出发时制造一个分身，但所有人共用体力。要求最小化货物从产生到运抵 B 期间损失的总价值，并输出一组合法运输方案。

解题思路

一次完整往返的路程恒为 2x。考虑任意时刻已经走过的总路程，再加上所有在途人员返回 A 所需的路程。该总和恰好等于已开始的往返次数乘 2x。因此能够开始的运输次数至多为：

若存在货物而 q=0，任何人都无法完成一次往返，答案为无解。

考虑位于 a_i 的工厂中，在时刻 t_{i,j} 产生的一件货物。定义它的出发时间下界为：

若某次运输在时刻 d 从 A 出发，它会在 d+a_i 到达该工厂。因此，这次运输能够收走该货物，当且仅当 d\ge s_{i,j}。

货物在 d+x 到达 B，从产生到抵达所用的时间可以拆成：

其中 x-a_i 只与工厂位置有关。设货物总数为 M，所有货物带来的固定损失为：

接下来只需最小化所有货物的 d-s_{i,j} 之和，最后再乘 m。

把所有 s_{i,j} 排序，记为 s_1\le s_2\le\dots\le s_M。按照出发时刻递增考虑每次运输。较早满足条件的货物必然不会晚于较晚满足条件的货物被收走。因此，每次运输收走的是尚未处理货物的一段前缀。整个方案对应于将有序序列划分成若干连续段。

若一段的右端点为 j，本次出发必须满足 d\ge s_j。取 d=s_j 已经能收走整段，继续推迟只会增加损失。因此，划分确定后，每段的最优出发时刻也随之唯一确定。

把一个非空段拆成相邻的两个非空段。让两次运输分别在各自右端点的 s 值出发。前一段的货物只可能更早到达，后一段的损失不变。因此，增加运输次数不会使最优值变差。实际使用的运输次数应为：

设前缀和为 S_j=\sum_{i=1}^j s_i。令 f_{r,j} 表示恰好用 r 次运输收走前 j 件货物时的最小值。DP 只计算可变等待时间之和。

若最后一段为 p+1\sim j，它们都在时刻 s_j 被收走。这一段的贡献为：

所以转移为：

整理与 p 有关的部分：

把每个决策点 p 看成一条直线。它的斜率为 -p，截距为 f_{r-1,p}+S_p，查询横坐标为 s_j。随着 p 增大，斜率单调递减；随着 j 增大，查询横坐标单调不降。于是可以用双端队列维护下凸壳，将一层转移降至 O(M)。

判断直线是否无用时，直接比较交点的先后关系。交叉乘积使用 __int128 计算，避免浮点误差和整数溢出。DP 只需保存相邻两层。另用 pre_{r,j} 记录最优决策点，便可从 (R,M) 倒推所有分段。

倒推得到的每个右端点对应一次出发，其绝对出发时刻就是该端点的 s_j。题目要求输出相对于求助时刻的时间，所以还要减去 k。

最后确定每次出发由谁完成。用小根堆维护所有已经出现的人的返家时刻，并先放入一个负无穷表示本体。按时间顺序处理出发事件：若最早返家的人已经可用，就让他再次出发；否则本次制造一个分身。每次出发至多制造一个分身，恰好符合题意。

还需说明此构造始终满足共享体力限制。开始第 z 次运输后，先计算所有人已经行走的总路程。再加上全部在途人员返回 A 仍需行走的总路程，结果恒为 2xz。由于 z\le R\le q，有：

所以任意时刻剩余体力都足以让所有在途人员回家。

时间复杂度为 O(n+M\log M+RM)，空间复杂度为 O(RM)。其中 R\le100，M\le2\times10^5。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
__extension__ using i128=__int128;
const int N=200005;
const int K=105;
const ll inf=4000000000000000000LL;
struct Line
{
    int k;
    ll b;
}h[N];
int a[N],b[N],pre[K][N];
ll s[N],sum[N],f[2][N];
ll get(Line z,ll x)
{
    return z.b-z.k*x;
}
bool bad(Line u,Line v,Line w)
{
    return (i128)(v.b-u.b)*(w.k-v.k)>=(i128)(w.b-v.b)*(v.k-u.k);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,x,c,k;
        cin>>n>>m>>x>>c>>k;
        for(int i=1;i<=n;i++)cin>>a[i];
        int cnt=0;
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>b[i];
            cnt+=b[i];
            ans+=(ll)b[i]*m*(x-a[i]);
        }
        int len=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=b[i];j++)
            {
                int v;
                cin>>v;
                s[++len]=v-a[i];
            }
        }
        if(!cnt)
        {
            cout<<0<<'\n';
            cout<<-1<<' '<<-1<<'\n';
            continue;
        }
        int r=c/(2*x);
        if(!r)
        {
            cout<<-1<<'\n';
            continue;
        }
        r=min(r,cnt);
        sort(s+1,s+cnt+1);
        for(int i=1;i<=cnt;i++)sum[i]=sum[i-1]+s[i];
        f[0][0]=0;
        fill(f[0]+1,f[0]+cnt+1,inf);
        for(int i=1;i<=r;i++)
        {
            int now=(i-1)&1,nxt=i&1;
            int head=0,tail=0;
            h[0]={i-1,f[now][i-1]+sum[i-1]};
            for(int j=i;j<=cnt;j++)
            {
                while(head<tail&&get(h[head],s[j])>=get(h[head+1],s[j]))head++;
                int p=h[head].k;
                f[nxt][j]=f[now][p]+(j-p)*s[j]-sum[j]+sum[p];
                pre[i][j]=p;
                if(f[now][j]>=inf/2)continue;
                Line z={j,f[now][j]+sum[j]};
                while(head<tail&&bad(h[tail-1],h[tail],z))tail--;
                h[++tail]=z;
            }
        }
        ans+=f[r&1][cnt]*m;
        cout<<ans<<'\n';
        vector<ll> dep;
        int pos=cnt;
        for(int i=r;i;i--)
        {
            dep.push_back(s[pos]);
            pos=pre[i][pos];
        }
        reverse(dep.begin(),dep.end());
        priority_queue<ll,vector<ll>,greater<ll>> q;
        q.push(-inf);
        for(ll v:dep)
        {
            int clone=1;
            if(q.top()<=v)
            {
                clone=0;
                q.pop();
            }
            cout<<v-k<<' '<<clone<<'\n';
            q.push(v+2*x);
        }
        cout<<-1<<' '<<-1<<'\n';
    }
    return 0;
}