列表

详情

NC51205. Cats Transport

描述

Zxr960115 is owner of a large farm. He feeds m cute cats and employs p feeders. There's a straight road across the farm and n hills along the road, numbered from 1 to n from left to right. The distance between hill i and (i - 1) is di meters. The feeders live in hill 1.
One day, the cats went out to play. Cat i went on a trip to hill hi, finished its trip at time ti, and then waited at hill hi for a feeder. The feeders must take all the cats. Each feeder goes straightly from hill 1 to n without waiting at a hill and takes all the waiting cats at each hill away. Feeders walk at a speed of 1 meter per unit time and are strong enough to take as many cats as they want.
For example, suppose we have two hillsand one cat that finished its trip at time 3 at hill 2 . Then if the feeder leaves hill 1 at time 2 or at time 3, he can take this cat, but if he leaves hill 1 at time 1 he can't take it. If the feeder leaves hill 1 at time 2, the cat waits him for 0 time units, if the feeder leaves hill 1 at time 3, the cat waits him for 1 time units.
Your task is to schedule the time leaving from hill 1 for each feeder so that the sum of the waiting time of all cats is minimized.

输入描述

The first line of the input contains three integers n, m, p .
The second line contains n - 1 positive integers 
Each of the next m lines contains two integers h_i and t_i.

输出描述

Output an integer, the minimum sum of waiting time of all cats.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.

示例1

输入: 

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

输出: 

3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 308ms, 内存消耗: 90064K, 提交时间: 2022-08-12 12:08:15 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=100010;
int n,m,p;
LL d[N],a[N],f[110][N],s[N],t[N];
int q[N];
LL get_y(int j,int k)
{
    return f[j-1][k]+s[k];
}
int main(){
    cin>>n>>m>>p;
    for(int i=2;i<=n;++i)
        cin>>d[i],d[i]+=d[i-1];
    for(int i=1;i<=m;++i)
    {
        int h;
        cin>>h>>t[i];
        a[i]=t[i]-d[h];
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=m;++i) s[i]=a[i]+s[i-1];
    memset(f,0x3f,sizeof f);
    for(int i=0;i<=p;++i) f[i][0]=0;
    for(int j=1;j<=p;++j)
    {
        int hh=0,tt=0;
        for(int i=1;i<=m;++i)
        {
            while(hh!=tt&&(get_y(j,q[hh+1])-get_y(j,q[hh]))<=(a[i])*(q[hh+1]-q[hh])) hh++;
            int k=q[hh];
            f[j][i]=f[j-1][k]+(i-k)*a[i]-s[i]+s[k];
            while(hh!=tt&&(get_y(j,q[tt])-get_y(j,q[tt-1]))*(i-q[tt-1])>=(get_y(j,i)-get_y(j,q[tt-1]) )*(q[tt]-q[tt-1])) tt--;
            q[++tt]=i;
        }
    }
    LL res=1e18;
    for(int i=1;i<=p;++i){
        res=min(res,f[i][m]);
    }
    cout<<res<<endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 308ms, 内存消耗: 89664K, 提交时间: 2020-09-24 09:53:33 

  
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[110][100010],s[100010],a[100010],d[100010],q[100010],g[100010];
int n,m,p,i,j,k,l,r;
int main()
{
	cin>>n>>m>>p;
	for(i=2;i<=n;i++)
	{
		cin>>j;
		d[i]=d[i-1]+j;
	}
	for(i=1;i<=m;i++)
	{
		cin>>j>>k;
		a[i]=k-d[j];
	}
	sort(a+1,a+m+1);
	for(i=1;i<=m;i++) s[i]=s[i-1]+a[i];
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(i=1;i<=p;i++)
	{
		for(j=1;j<=m;j++) g[j]=f[i-1][j]+s[j];
		q[l=r=1]=0;
		for(j=1;j<=m;j++)
		{
			while(l<r&&g[q[l+1]]-g[q[l]]<=a[j]*(q[l+1]-q[l])) l++;
			f[i][j]=min(f[i-1][j],g[q[l]]+a[j]*(j-q[l])-s[j]);
			if(g[j]>=0x3f3f3f3f3f3f3f3fll) continue;
			while(l<r&&(g[j]-g[q[r]])*(q[r]-q[r-1])<=(g[q[r]]-g[q[r-1]])*(j-q[r])) r--;
			q[++r]=j;
		}
	}
	cout<<f[p][m]<<endl;
}

C++ 解法, 执行用时: 317ms, 内存消耗: 89668K, 提交时间: 2022-02-01 15:06:07 

#include<bits/stdc++.h>
using namespace std;
long long q[100001],f[110][100001],sumd[100001],s[100001],a[100001],g[100001],h,t,n,m,p,x,l,r;
int main(){
	cin>>n>>m>>p;
	for(long long i=2;i<=n;i++)cin>>x,sumd[i]=sumd[i-1]+x;
	for(long long i=1;i<=m;i++)cin>>h>>t,a[i]=t-sumd[h];
	sort(a+1,a+m+1);
	for(long long i=1;i<=m;i++)s[i]=s[i-1]+a[i];
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(long long i=1;i<=p;i++){
		for(long long j=1;j<=m;j++)g[j]=f[i-1][j]+s[j];
		l=0,r=0;q[0]=0;
		for(long long j=1;j<=m;j++){
			while(l<r&&g[q[l+1]]-g[q[l]]<a[j]*(q[l+1]-q[l]))l++;
			f[i][j]=g[q[l]]+(j-q[l])*a[j]-s[j];
			while(l<r&&(g[q[r]]-g[q[r-1]])*(j-q[r])>=(g[j]-g[q[r]])*(q[r]-q[r-1]))r--;
			q[++r]=j;
		}
	}
	cout<<f[p][m];
	return 0;
}

上一题

© 2024 nowcoder.com