【题解】CF311B Cats Transport

· · 个人记录 

/*
对于第i只猫，求出t[i]，表示正好接到它的铲屎官的出发时间
易证得铲屎官的出发时间必定是t[i]
解释：
如果出发时间不是t[i]，那么所有能被他接到的猫都是等待了一段时间之后的。
如果铲屎官的时间提前到正好接到t[i]最小的那一只猫，则接到的猫不变，但时间更优
设第i个铲屎官在t[j]时刻出发，第i-1个铲屎官在t[k]时刻出发
增加的等待时间为∑[k＜l≤j]t[l]-t[j]
设sum[i]表示t[1]+t[2]+...+t[i]
则增加的等待时间为(j-k)*t[j]-(sum[j]-sum[k])
设f[i][j]表示前i个铲屎官，第i个铲屎官在t[j]时刻出发的最小等待时间
f[i][j]=f[i-1][k]-sum[j]+sum[k]+(j-k)*t[j]
f[i][j]=f[i-1][k]-sum[j]+sum[k]+j*t[j]-k*t[j]
f[i][j]+k*t[j]+sum[j]-j*t[j]=f[i-1][k]+sum[k]
f[i-1][k]+sum[k]=k*t[j]+sum[j]-j*t[j]+f[i][j]
y               =k*x   +b

设a比b优
f[i-1][a]-sum[j]+sum[a]+(j-a)*t[j]<=f[i-1][b]-sum[j]+sum[b]+(j-b)*t[j]
f[i-1][a]+sum[a]-a*t[j]<=f[i-1][b]+sum[b]-b*t[j]
f[i-1][a]-f[i-1][b]<=-sum[a]+sum[b]+a*t[j]-b*t[j]
f[i-1][a]+sum[a]-f[i-1][b]-sum[b]<=(a-b)*t[j]
(f[i-1][a]+sum[a]-f[i-1][b]-sum[b])/(a-b)<=t[j]

设slope[i]=f[i-1][a]+sum[a]
(slope[a]-slope[b])/(a-b)<=t[j]

设g[a,b]=(slope[a]-slope[b])/(a-b)
若g[a,b]≤t[j]，则b比a优，否则a比b优
若g[a,b]≥g[b,c](a<b<c)
    1.g[b,c]≤t[j] ，则c比b优，可以舍弃b
    2.g[b,c]≥t[j] ，则g[a,b]≥t[i] ，则a比b优，可以舍弃b
综上所述，当 g[a,b]>=g[b,c](a<b<c)时，可以舍弃b
相当于维护一个下凸壳，用队列维护即可
*/
#include<bits/stdc++.h>
#define MAXN 100005
#define MAXM 100005
#define MAXP 105
#define ll long long
using namespace std;

ll n,m,p;
ll d[MAXN],t[MAXM],sum[MAXM],h;
ll f[MAXP][MAXN];
ll q[MAXN],l,r;

double slope(ll i,ll j)
{return (double)(f[i-1][j]+sum[j]);}
double g(ll i,ll a,ll b)
{
    if(a==b) return 1e16;
    double s1=slope(i,a),s2=slope(i,b);
    if(abs(s1-s2)<=1e-9) return 0;
    return (double)((s1-s2)/((double)(a-b)));
}
ll work(ll i,ll j)
{
    while(l<r&&g(i,q[l],q[l+1])<(double)t[j]) l++;//cout<<"l++ "<<g(i,q[l],q[l+1])<<"<="<<t[j]<<endl
    return q[l];
}
void add(ll i,ll j)
{
    while(l<r&&g(i,q[r-1],q[r])>=g(i,q[r],j)) r--;//,cout<<"r--\n";
//  cout<<g(q[r-1],q[r])<<" "<<g(q[r],i)<<endl;
    q[++r]=j;//cout<<"r++\n";
}
int main()
{
    cin>>n>>m>>p;
    //m只猫n座山p个人 
    for(ll i=2;i<=n;i++)
    {
        cin>>d[i];
        d[i]+=d[i-1];
    }
    for(ll i=1;i<=m;i++)
    {
        cin>>h>>t[i];
        t[i]=t[i]-d[h];
        sum[i]=sum[i-1]+t[i];
    }
    sort(t+1,t+1+m);
    for(ll i=1;i<=m;i++)
        sum[i]=sum[i-1]+t[i];
//  for(ll i=1;i<=m;i++)cout<<t[i]<<" ";cout<<endl;
    for(ll j=1;j<=m;j++)
        f[1][j]=t[j]*j-sum[j];//,cout<<"f[1]["<<j<<"]="<<f[1][j]<<endl;
    ll ans=1e16;
    for(ll i=2;i<=p;i++)
    {
        l=r=0;q[l]=0;
        for(ll j=1;j<=m;j++)
        {
            ll k=work(i,j);
            f[i][j]=f[i-1][k]-sum[j]+sum[k]+(j-k)*t[j];
//          cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<" k="<<k<<endl;
            add(i,j);
        }
        ans=min(ans,f[i][m]);
    }
    cout<<ans;
    return 0;
}