当前位置:首页 >> 学科竞赛 >>

noip2011


【问题描述】 风景迷人的小城 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 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小? 【输入】 输入文件名为 bus.in。 第 1 行是 3 个整数 n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和 氮气加速器个数。 第 2 行是 n-1 个整数,每两个整数之间用一个空格隔开,第 i 个数表示从第 i 个景点开往 第 i+1 个景点所需要的时间,即 Di。 第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi,每两个整数之间用一个空格隔开。第 i+2 行表 示第 i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。 【输出】 输出文件名为 bus.out。共一行,包含一个整数,表示最小的总旅行时间。 【输入输出样例】 bus.in bus.out 332 14 013 112 523 10 【输入输出样例说明】 对 D2 使用 2 个加速器,从 2 号景点到 3 号景点时间变为 2 分钟。 公交车在第 1 分钟从 1 号景点出发, 第 2 分钟到达 2 号景点, 第 5 分钟从 2 号景点出发, 第 7 分钟到达 3 号景点。 第 1 个旅客旅行时间 7-0 = 7 分钟。 第 2 个旅客旅行时间 2-1 = 1 分钟。 第 3 个旅客旅行时间 7-5 = 2 分钟。 总时间 7+1+2 = 10 分钟。 【数据范围】 对于 10%的数据,k=0;

对于 20%的数据,k=1; 对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m≤ 1,000,0 ≤ k ≤ 20,0 ≤ Di ≤ 10,0 ≤ Ti ≤ 500; 对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m≤ 1,000,0 ≤ k ≤ 100,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 10,000; 对于 100%的数据, 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 10,000, 0 ≤ k ≤ 100,000, 0 ≤ Di ≤ 100,0 ≤ Ti ≤ 100,000。

每次递推出来到达 i 站的时间,判断从 i 站出发的时间是否比到达 i 站晚,如果从 i 站出发 的时间比到达 i 站晚 (这句话的意思就是汽车到达

i 站的时间比在 i 站上车

的最后一个到达的乘客还要晚, 这样子就要使用氮气加速器, 以缩短 汽车从 i-1 站到 i 站行驶的时间) ,则可以考虑把氮气加速器用在 i-1 站到 i 站,在
可以使用氮气加速器的地方判断影响范围有多大,在影响最大的地方使用氮气加速器, dec(k),然后再循环,一直到 k=0…… program bus; var n,m,k,i,j,tt,tz,dd,da,dz,mn:longint; a,b,c,d,mm,num,time,yx:array[0..10000] of longint; ans:longint; function max(q,p:longint):longint; begin if q>p then exit(q); exit(p); end; function min(q,p:longint):longint; begin if q>p then exit(p); exit(q); end; function sum(q,p:longint):longint; var i,ans:longint; begin ans:=0; for i:=p+1 to q do inc(ans,num[i]); exit(ans); end; begin assign(input,'bus.in');reset(input); assign(output,'bus.out');rewrite(output);

readln(n,m,k); for i:=1 to n-1 do read(d[i]); for i:=1 to m do begin readln(a[i],b[i],c[i]); if mm[b[i]]<a[i] then mm[b[i]]:=a[i]; inc(num[c[i]]); end;

//记录从 i 站到达 i+1 站所用时间 //记录每个人旅行的信息

//统计最后一个从 b[i]站上车的时间(预处理 //统计从 c[i]站下车的人数(预处理

while true do begin time[1]:=0; //汽车到达第一个站的时间为 0 for i:=2 to n do //递推到达 i 站的时间 time[i]:=max(time[i-1],mm[i-1])+d[i-1];//如果是汽车等人(汽车先到站,则取最后一个 到站的乘客的时间,否则就取汽车到站的时间(人等汽车,人都到齐了,汽车还没有到) yx[n]:=n; // 判断修改 i 到 i+1 所用时间影响的范围 for i:=n-1 downto 1 do begin yx[i]:=yx[i+1]; if time[i+1]<=mm[i+1] then yx[i]:=i+1; end; tt:=1; while (d[tt]=0)and(tt<=n-1) do inc(tt); if(tt=n)or(k=0)then break; for i:=tt+1 to n-1 do //找出影响范围最大的(影响的人的个数) if (d[i]<>0)and(sum(yx[tt],tt)<sum(yx[i],i)) then tt:=i; if sum(yx[tt],tt)=0 then break; dd:=maxlongint; //减去最小的 time[i]-mm[i],使后面不会出现 mm[i]>time[i]的情况 for i:=tt+1 to yx[tt]-1 do dd:=min(dd,time[i]-mm[i]); dd:=min(dd,k); dd:=min(dd,d[tt]); k:=k-dd; d[tt]:=d[tt]-dd; end;

for i:=1 to m do inc(ans,time[c[i]]-a[i]); writeln(ans); close(input); close(output); end.

//统计每个人旅行的时间

给你 k 个氮气加速器,求乘客的旅行时间最小值。 maxArrive i 表示从 i 点出发的人,Ti 的最大值,即最迟到达时间,无人出发 则为 0。enter i 表示 i 点的最早到达时间,那么 enter i=max{enter i-1,maxArrive i-1}+Di-1 那么消耗的总时间就是 sum((enter bi) – Ti)(1<=i<=m) 循环 k 次。每次枚举 i∈[1,m],计算 Di=(Di)-1 (Di>=1)后的总时间,从中找 一个时间最少的进行下一步即可。(贴吧上的,正确性值得探讨) 【时间复杂度】


相关文章:
NOIP2011 提高组 day1 试题
NOIP2011 提高组 day1 试题_其它考试_资格考试/认证_教育专区。NOIP,2011,DAY1,提高组,试题 文档贡献者 91oi 贡献于2011-11-13 ...
noip2011初赛试题及答案(完美Word版)
noip2011初赛试题及答案(完美Word版)_英语考试_外语学习_教育专区 暂无评价|0人阅读|0次下载|举报文档noip2011初赛试题及答案(完美Word版)_英语考试_外语学习_教育...
NOIP2011普及组解题报告
NOIP2011普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2011 普及组解题报告一、数字反转 没得满分只能说明一个问题,你的程序写的太少了。 program reverse; ...
第十七届NOIP2011 提高组初赛试题及答案解析
第十七届NOIP2011 提高组初赛试题及答案解析_计算机硬件及网络_IT/计算机_专业资料。第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 提组 Pascal 语言 两小时完成...
NOIP2011DAY2解题报告
NOIP2011DAY2 解题报告 ——by 北京一零一中学 张子威(c++) 今天的题还蛮有意思的,虽然做的没有昨天好吧,随便写两笔,可能是我 OI 生 涯最后一份解题报告了...
NOIP2011提高组解题报告day1
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地...
NOIP2011提高组解题报告day2
NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 计算系数 【问题描述】 给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(...
noip2011普及组初赛试题与答案
noip2011普及组初赛试题与答案_IT/计算机_专业资料。noip2011普及组初赛试题与答案 2011 年第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 Pascal 语言 两...
NOIP2011提高组初赛试题及答案C++版
A.阶码 B.补码 C.反码 D.较长的尾数 NOIP2011 初赛 提高组 C++ 2 9.对右图使用 Dijkstra 算法计算 S 点到其余各点的最短路径长度时,到 B 点的 距离 d...
NOIP2011第十七届初赛Pascal普及组试题与答案(Word)
B、约翰·冯·诺依曼奖 C、图灵奖 D、高德纳奖(Donald E. Knuth Prize) CCF NOIP2011 初赛 2 普及组 Pascal 19、对一个有向图而言,如果每个节点都存在到达...
更多相关标签:
noip2011普及组复赛 | noip2011 day2 | noip | noip2010 | noip2011提高组 | noip2011提高组初赛 | noip2011提高组复赛 | noip2011普及组初赛 |