NC16598. [NOIP2011]观光公交
描述
输入描述
第1行是3个整数n,m,k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。
第2行是n-1个整数，每两个整数之间用一个空格隔开，第i个数表示从第i个景点开往第i+1个景点所需要的时间，即Di。
第3行至m+2行每行3个整数Ti,Ai,Bi，每两个整数之间用一个空格隔开。第i+2行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。
输出描述
共一行，包含一个整数，表示最小的总旅行时间。
示例1
输入:
3 3 2 1 4 0 1 3 1 1 2 5 2 3
输出:
10
说明:
对D2使用2个加速器，从2号景点到3号景点时间变为2分钟。C++14(g++5.4) 解法, 执行用时: 156ms, 内存消耗: 528K, 提交时间: 2019-08-31 16:38:40
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k,d[1002],tim[10002],st[10003],ed[10003],car[1002],g[1002],t[1002],sum[1002];
int ans,fast,maxnn;
int main(){
scanf("%d%d%d",&n,&m,&k);//jingdian 乘客 氮气
for(int i=1;i<n;i++)scanf("%d",&d[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&tim[i],&st[i],&ed[i]);
t[st[i]]=max(t[st[i]],tim[i]);
sum[ed[i]]++;
}
for(int i=2;i<=n;i++)sum[i]+=sum[i-1];
car[1]=t[1];
for(int i=2;i<=n;i++){car[i]=max(car[i-1],t[i-1])+d[i-1];}
for(int i=1;i<=m;i++)ans+=(car[ed[i]]-tim[i]);
while(k--){
g[n]=g[n-1]=n;maxnn=0;
for(int i=n-2;i>=1;i--)
g[i]=car[i+1]<=t[i+1]?i+1:g[i+1];
for(int i=1;i<n;i++)
if(sum[g[i]]-sum[i]>maxnn&&d[i]){
maxnn=sum[g[i]]-sum[i];fast=i;
}
ans-=maxnn;d[fast]--;
for(int i=2;i<=n;i++)car[i]=max(car[i-1],t[i-1])+d[i-1];
}
printf("%d\n",ans);
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 46ms, 内存消耗: 608K, 提交时间: 2022-11-27 20:50:01
#include<bits/stdc++.h>
#define maxn 1000
#define maxm 10000
using namespace std;
int n,m,k,d[maxn+20],t[maxm+20],a[maxm+20],b[maxm+20],people[maxn+20],go[maxn+20],arrive[maxn+20];
int main(){
int i,j,x,y,z,ans=0;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<n;i++) scanf("%d",&d[i]);
for(i=1;i<=m;i++){
scanf("%d%d%d",&t[i],&a[i],&b[i]);
people[b[i]-1]++;
go[a[i]]=max(go[a[i]],t[i]);
}
for(i=2;i<=n;i++)
arrive[i]=max(go[i-1],arrive[i-1])+d[i-1];
while(k--){
x=y=z=0;
for(j=n;j>1;j--){
if(arrive[j]<=go[j])z=0;
z+=people[j-1];
if(d[j-1]>0&&z>x)x=z,y=j-1;
}
if(y==0)break;d[y]--;
for(i=y+1;i<=n;i++)arrive[i]=max(arrive[i-1],go[i-1])+d[i-1];
}for(i=1;i<=m;i++)ans+=arrive[b[i]]-t[i];
printf("%d\n",ans);
}