Cats Transport

CF

洛咕

Vjudge

题意:小S是一个大农场主.他养了m只可爱的猫,雇佣了p个饲养员.农场中有一条笔直的路,路边有N座山,从1到N编号.山丘i与山丘i-1的距离是\(d_i\)米.饲养员都住在1号山丘.一天,猫外出玩耍.猫i去山丘\(h_i\)游玩,在\(t_i\)时间结束他的游玩,然后在原地傻等饲养员.饲养员必须把所有的猫带回.每个饲养员直接从1号山走到N号山,不花费时间的把已经游玩结束的猫带回.每个铲屎官的速度为一米每单位时间,并且足够强壮来带上任意数量的猫.举个栗子,假装我们有两个相距为1的山丘,有一只猫,他想去山丘2玩到时间3.然后饲养员如果在时间2或者时间3从1号山丘出发,他就能抱走猫.如果他在时间1出发那么就不行(猫子还在玩耍).如果饲养员在时间2出发,猫就不用等他(ΔT=0).如果他在时间3出发,猫就要等他1个单位时间。你的任务是安排每个饲养员出发的时间,最小化所有猫等待的时间之和.

分析:对于每只猫,设\(A[i]=t[i]-\sum_{j=1}^{h[i]}d[j]\),一名饲养员如果想接到第i只猫,就必须要在\(A[i]\)时刻之后从1号山出发.若出发时刻为t,则猫的等待时间就是\(t-A[i]\)

预处理出A数组,并从小到大排序,这样一个饲养员接走的猫一定是连续的一群,这样本题就是斜率优化的模板题了.

设\(f[i][j]\)表示前i个饲养员接走前j只猫的最小等待时间,则有,

\(f[i][j]=f[i-1][k]+A[j]*(j-k)-(S[j]-S[k])\)其中S数组是A数组排好序后的前缀和数组

设l<k且k比l更优,即

\(f[i-1][k]+A[j]*(j-k)-(S[j]-S[k])<f[i-1][l]+A[j]*(j-l)-(S[j]-S[l])\)

整理一下上式得到,

\(\frac{f[i-1][k]+S[k]-f[i-1][l]-S[l]}{k-l}<A[j]\)

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
const int N=200005;
const int M=100005;
int d[N],h[M],t[M],q[N];
LL D[N],sum[M],a[M],f[105][M];
int main(){
    int n=read(),m=read(),p=read();
    for(int i=2;i<=n;i++){
        d[i]=read();
        D[i]=D[i-1]+d[i];
    }
    for(int i=1;i<=m;i++){
        h[i]=read();t[i]=read();
        a[i]=t[i]-D[h[i]];
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)sum[i]=sum[i-1]+a[i];
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=p;i++)f[i][0]=0;
    for(int i=1;i<=p;i++){
        int l=1,r=1;q[1]=0;
        for(int j=0;j<=m;j++){
            while(l<r&&(f[i-1][q[l+1]]+sum[q[l+1]])-(f[i-1][q[l]]+sum[q[l]])<=(q[l+1]-q[l])*a[j])l++;
            f[i][j]=f[i-1][q[l]]+sum[q[l]]+a[j]*j-sum[j]-a[j]*q[l];
            while(l<r&&((f[i-1][q[r]]+sum[q[r]])-(f[i-1][q[r-1]]+sum[q[r-1]]))*(j-q[r])>=((f[i-1][j]+sum[j])-(f[i-1][q[r]]+sum[q[r]]))*(q[r]-q[r-1]))r--;
            q[++r]=j;
        }
    }
    printf("%lld\n",f[p][m]);
    return 0;
}
上一篇:Cats Transport


下一篇:【题解】Cats Transport (斜率优化+单调队列)