$Sol$
觉得这题贪心要想很多事情,不适合我这种没脑子选手$ovo$.看题解还理解了很久.
最开始是这样想的:把所有的路段上的乘客按大小排个序用加速器就好了,这个想法被自己轻松$hack.$因为,假如一个路段的终点没人下车而且又要等乘客很久才能出发,那前面用加速器也没意义了.由这个反例似乎可以推出用$1$个加速器能减少的时间?由这个起点向后枚举点,看用了加速器到达后是否还需要等乘客,如果不是,那么这个加速器对于这站下车的乘客就是有帮助的.由此也可以看出用加速器之后可能会对后面的出发时间有影响,这里需要一个变量来维护.
具体来说:
$off[i]$表示第$i$站下车的乘客数量.
$arr[i]$表示第$i$站乘车的乘客的最晚到达时间.
$dd[i]$表示汽车到达$i$站的时间.
$d[i]$表示第$i$站到第$i+1$站所需要的时间.
$dd[i]=max(dd[i-1],arr[i-1])+d[i-1].$
$aff[i]$表示假设$(i,i+1)$这段路程所需时间减少$1$,那么在$aff[i]$下站的人是最后的受益者.
差不多就是维护上面的变量就好了,具体看代码叭.
$Code$
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define il inline #define Rg register #define go(i,a,b) for(Rg int i=a;i<=b;++i) #define yes(i,a,b) for(Rg int i=a;i>=b;--i) #define mem(a,b) memset(a,b,sizeof(a)) #define int long long #define db double #define inf 2147483647 using namespace std; il int read() { Rg int x=0,y=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*y; } const int N=1010; int n,m,k,as,off[N],arr[N],dd[N],sum[N],d[N],aff[N]; struct node{int t,u,v;}a[N*10]; main() { n=read(),m=read(),k=read(); go(i,1,n-1)d[i]=read(); go(i,1,m) { a[i]=(node){read(),read(),read()}; off[a[i].v]++; arr[a[i].u]=max(arr[a[i].u],a[i].t); } go(i,2,n)dd[i]=max(dd[i-1],arr[i-1])+d[i-1]; go(i,1,n)sum[i]=sum[i-1]+off[i]; go(i,1,m)as+=dd[a[i].v]-a[i].t; arr[n]=inf; while(k--) { int maxs=0,qwq=0; yes(i,n-1,1) if(dd[i+1]>arr[i+1])aff[i]=aff[i+1]; else aff[i]=i+1; go(i,1,n-1) if(sum[aff[i]]-sum[i]>maxs&&d[i]) maxs=sum[aff[i]]-sum[i],qwq=i; as-=maxs;d[qwq]-=1; go(i,2,n)dd[i]=max(dd[i-1],arr[i-1])+d[i-1]; } printf("%lld\n",as); return 0; }