【NOIP2011 Day 2】观光公交
【问题描述】
小城Y市,拥有n个景点。由于慕名而来的游客越来越多,Y市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点,随后依次前往2、3、4……n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻,公交车只能往前开,或在景点处等待。 设共有m个游客,每位游客需要乘车1次从一个景点到达另一个景点,第i 位游客在Ti分钟来到景点Ai,希望乘车前往景点Bi(Ai<Bi)。为了使所有乘客都能顺利到达目的地,公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。 一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机ZZ给公交车安装了k个氮气加速器,每使用一个加速器,可以使其中一个Di减1。对于同一个Di可以重复使用加速器,但是必须保证使用后Di大于等于0。
那么ZZ该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?
对于100%的数据,1≤n≤1,000,1≤m≤10,000,0≤k≤100,000,0≤Di ≤100,0≤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[];
int n,m,K,ans;
int f[],Time[],g[],dist[],sum[];
int main()
{
scanf("%d %d %d",&n,&m,&K);
for (int i = ;i < n;i ++)
scanf("%d",&dist[i]);
for (int i = ;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 = ;i <= n;i ++)
sum[i] += sum[i - ]; Time[] = ;
for (int i = ;i <= n;i ++)
Time[i] = max(Time[i - ],f[i - ]) + dist[i - ];
for (int i = ;i <= m;i ++)
ans += Time[a[i].target] - a[i].arrive; while (K)
{
g[n] = n;
g[n - ] = n;
for (int i = n - ;i ; i -- )
{
if (Time[i + ] <= f[i + ])
g[i] = i + ;
else g[i] = g[i + ];
}
int Max = ,j;
for (int i = ;i <= n;i ++)
if (sum[g[i]] - sum[i] > Max && dist[i] > )
Max = sum[g[i]] - sum[i],j = i;
if (!Max) break;
ans -= Max;
dist[j] --;
K --;
Time[] = ;
for (int i = ;i <= n;i ++)
Time[i] = max(Time[i - ],f[i - ]) + dist[i - ];
}
cout << ans;
}
最新文章
- RegQueryValueEx正确使用方法
- Chart图表
- IntelliJ IDEA的快捷键
- RabbitMQ、ActiveMQ和ZeroMQ
- Python CSV模块处理文件读写
- MongoDB的SSL实现分析
- Thread的第四天学习
- poj 1595
- BAPI总的数据库提交和回滚
- 从头开始学JavaScript (七)——函数
- Active Record Query Interface 数据查询接口(界面) 看到第8节。
- Redis主从数据库同步
- luogu P4779 【模板】单源最短路径(标准版)
- TCP、UDP数据包大小的限制
- js 模拟鼠标事件
- web项目中的路径问题
- CSS 背景background实例
- 你真的了解View的坐标吗?
- tar.gz 文件解压 (安装 netbean 时会用到)
- OpenGL6-纹理动画
热门文章
- linux 新添加的硬盘格式化并挂载到目录下
- OpenCV:OpenCV中的 parallel_for 和opencv parallel_for_
- 【sqli-labs】 less11 POST - Error Based - Single quotes- String (基于错误的POST单引号字符型注入)
- Swift库二进制接口(ABI)兼容性研究
- 【转】上拉下拉电阻、I/O输出(开漏、推挽等)
- PAT_A1109#Group Photo
- [kernel学习]----如何debug kernel
- IE与标准浏览器对事件处理的区别
- win10、win7 使用centos配置网络,可以让Xshell进行连接,虚拟机进行上网;
- QT5.4.1在ARM开发板上不能显示汉字