用wordpress做购物网站,网站免费网站的方法,wordpress 源码出售,宁波个人做网站【问题描述】 小城Y市#xff0c;拥有n个景点。由于慕名而来的游客越来越多#xff0c;Y市特意安排了一辆观光公交车#xff0c;为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点#xff0c;随后依次前往2、3、4……n号景点。从第i号景点开到第i1号景点需要D…【问题描述】 小城Y市拥有n个景点。由于慕名而来的游客越来越多Y市特意安排了一辆观光公交车为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点随后依次前往2、3、4……n号景点。从第i号景点开到第i1号景点需要Di分钟。任意时刻公交车只能往前开或在景点处等待。 设共有m个游客每位游客需要乘车1次从一个景点到达另一个景点第i 位游客在Ti分钟来到景点Ai希望乘车前往景点BiAiBi。为了使所有乘客都能顺利到达目的地公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。 一个乘客的旅行时间等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一观光车有时候还要停下来等其他乘客乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了k个氮气加速器每使用一个加速器可以使其中一个Di减1。对于同一个Di可以重复使用加速器但是必须保证使用后Di大于等于0。 那么ZZ该如何安排使用加速器才能使所有乘客的旅行时间总和最小 对于100%的数据1≤n≤1,0001≤m≤10,0000≤k≤100,0000≤Di ≤1000≤Ti≤100,000。 【分析】 设t[i]表示来到第i个景点的乘客最晚的时间time[i]表示车到达第i个景点的最小时间。 因为每个乘客到达的时间已经固定所以要使总时间最小就是使Σtime[b[i]]最小其中b[i]代表每位乘客的目的地。 先考虑不用加速器的情况。可以直接递推求出答案time[i] max(time[i - 1],t[i - 1]) d[i - 1]; 接下来再来考虑使用加速器减少的时间。对于每个加速器我们必须使这个加速器获得最大的效益即使尽可能多的乘客旅行时间减一。如果我们在i到i 1间使用加速器的话那么到i 1站的乘客的旅行时间都会减一但是如果time[i 1]小于t[i 1]的话车就要在i 1站等到t[i 1]所有的乘客上车在i 1站以后下车的乘客的时间是一样的也就是说这个加速器对后面下车的乘客没有影响。我们可以用递推求出每个i最远能影响的车站。 g[i] g[i 1] (time[i 1] t[i 1]) g[i] i 1 (time[i 1] t[i 1]) 那么我们用一个加速器所能减少一个单位时间的乘客就是sum[g[i]] - sum[i]每次找出使这个最大的i即可。然后把ans减掉维护time,g 这题说白了就是贪心。加速器的使用各不影响。易知这个贪心是正确的。 代码还是比较好写的。 【代码】 #include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
struct node
{int start,arrive,target;
}a[20000];
int n,m,K,ans;
int f[20000],Time[20000],g[20000],dist[20000],sum[20000];
int main()
{scanf(%d %d %d,n,m,K);for (int i 1;i n;i )scanf(%d,dist[i]);for (int i 1;i m;i ){scanf(%d %d %d,a[i].arrive,a[i].start,a[i].target);f[a[i].start] max(f[a[i].start],a[i].arrive);sum[a[i].target] ;}for (int i 2;i n;i )sum[i] sum[i - 1];Time[1] 0;for (int i 2;i n;i )Time[i] max(Time[i - 1],f[i - 1]) dist[i - 1];for (int i 1;i m;i )ans Time[a[i].target] - a[i].arrive;while (K){g[n] n;g[n - 1] n;for (int i n - 2;i ; i -- ){if (Time[i 1] f[i 1])g[i] i 1;else g[i] g[i 1];}int Max 0,j;for (int i 1;i n;i )if (sum[g[i]] - sum[i] Max dist[i] 0)Max sum[g[i]] - sum[i],j i;if (!Max) break;ans - Max;dist[j] --;K --;Time[1] 0;for (int i 2;i n;i )Time[i] max(Time[i - 1],f[i - 1]) dist[i - 1];}cout ans;
} 转载于:https://www.cnblogs.com/N-C-Derek/p/3371058.html
