vijos1741 观光公交 （贪心）
|
P1741观光公交
请登录后递交
描述风景迷人的小城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该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？ 格式输入格式第1行是3个整数n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。 第2行是n-1个整数，每两个整数之间用一个空格隔开，第i个数表示从第i个景点开往第i+1个景点所需要的时间，即Di。 第3行至m+2行每行3个整数Ti, Ai, Bi，每两个整数之间用一个空格隔开。第i+2行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。 输出格式共一行，包含一个整数，表示最小的总旅行时间。 限制1s 提示样例说明： 对D2使用2个加速器，从2号景点到3号景点时间变为2分钟。 公交车在第1分钟从1号景点出发，第2分钟到达2号景点，第5分钟从2号景点出发，第7分钟到达3号景点。 第1个旅客旅行时间7 - 0 = 7分钟； 总时间7 + 1 + 2 = 10分钟。 数据范围： 对于10%的数据，k = 0； 来源NOIp2011提高组Day2第三题 |
大意：题目说得很清楚，我都怕。
题解：贪心，一个个选择氮气加速的位置。
首先我们看乘客所花时间和怎么计算，容易得到一个乘客所花的时间等于
ar[b[i]] - T[i]
其中b[i]为该乘客的终点，ar[x]为到达x站的时间，T[i]为该乘客出发的时间。
我们把到达x的乘客统计，cntto[x]为到达x的乘客的数量，然后所有乘客所花的时间和，就是sum(cntto[i]*ar[i])-sumT，cntto和sum都是已知的，关键在于ar。
设st[i]为从i出发的最晚一名游客的出现时间，这样我们可以用st[i]和d[i]来从头到尾得到各个点的ar[i]。
for(i=; i<n; i++) artime[i]=max(artime[i-],st[i-])+d[i-];
然后我们一个个氮气加速分别考虑，每次贪心放在能减少时间总和最多的位置。对每个位置计算，向后推若干个ar[i]>st[i]，即有发展潜力的位置，（若ar[i]<=st[i]，则减少ar[i]也无法减少之后游客的时间）。
for(i=; i<n-; i++) {
if(d[i]>) {
canup=cntto[i+];
j=i+;
while(j+<n && artime[j]>st[j])canup+=cntto[j+],j++;
//cout<<i<<','<<j<<endl;
if(canup>maxup) {
maxup=canup;
maxi=i;
}
}
}
这样我们就在maxi处氮气加速，效果最碉。
重复多次，用完所有氮气加速，完成。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usint unsigned int
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout) const int maxn=;
const int maxm=;
int d[maxn],T[maxm],a[maxm],b[maxm];
int st[maxn],artime[maxn];
int cntto[maxn];
int canup[maxn];
int n,m,k;
ll Tsum; int main() {
int i,j;
int maxi,maxup,canup;
ll ans;
while(scanf("%d%d%d",&n,&m,&k)!=EOF) {
REP(i,n-) scanf("%d",&d[i]);
mz(st);
mz(cntto);
Tsum=;
REP(i,m) {
scanf("%d%d%d",&T[i],&a[i],&b[i]);
a[i]--;b[i]--;
if(st[a[i]]<T[i])st[a[i]]=T[i];
cntto[b[i]]++;
Tsum+=T[i];
}
artime[]=;
for(i=; i<n; i++) artime[i]=max(artime[i-],st[i-])+d[i-];
while(k>) {
maxi=-;
maxup=-;
for(i=; i<n-; i++) {
if(d[i]>) {
canup=cntto[i+];
j=i+;
while(j+<n && artime[j]>st[j])canup+=cntto[j+],j++;
//cout<<i<<','<<j<<endl;
if(canup>maxup) {
maxup=canup;
maxi=i;
}
}
}
d[maxi]--;
//printf("WOW,%d!",maxi);
artime[]=;
k--;
for(i=; i<n; i++) artime[i]=max(artime[i-],st[i-])+d[i-];
}
ans=-Tsum;
for(i=; i<n; i++)
ans+=artime[i]*cntto[i];
printf("%lld\n",ans);
}
return ;
}
最新文章
- webform开发基础
- Windows VC++常见问题汇总
- C#操作Access
- 去掉有序数组中重复数字 原地 leetcode java (最简单的方法)
- WebAPI 用ActionFilterAttribute实现token令牌验证与对Action的权限控制
- java学习笔记——IO部分（遍历文件夹）
- 面试常用算法总结——排序算法（java版）
- python爬虫入门（八）Scrapy框架之CrawlSpider类
- Linux常用命令详解（week1_day1_1）--技术流ken
- Python量化交易
- BrowserSync前端同步测试工具
- Sublime Text 之运行 js 方法[2015-5-6更新mac下执行js]
- 51nod 1443 路径和树（最短路）
- php的几个实用正则表达式
- user_add示例
- Keil出错解决方法
- Maven：Generating Project in Batch mode 卡住问题
- 使用cmd命令创建vue（ivieiw）项目
- ios PNG Crush error （PNG图片错误）
- jQuery EasyUI Datagrid组件默认视图分析