noip2014普及组初赛答案_观光3路公交车路线

noip2014普及组初赛答案_观光3路公交车路线风景迷人的小城Y市,拥有n个美丽的景点。由于慕名而来的游客越来越多,Y市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点,随后依次前往2、3、4……n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻,公交车只能往前开,或在景点处等待。设共有m个游客,每位游客需要乘车1次从一个景点到达另一个景点,第i位游客在Ti分钟来到景点Ai,希望乘车前往景点Bi(Ai

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

noip2014普及组初赛答案_观光3路公交车路线

noip2014普及组初赛答案_观光3路公交车路线

noip2014普及组初赛答案_观光3路公交车路线

program bus;
 CONST
       maxn=1000;
       maxm=10000;
       maxk=1000000;
 var a,b,t:array[0..maxm] of longint;//a,b,t三个数组分别表示游客上车站,下车站以及到达时间
     right,tot,s,cnt,GetIn,GetOff,get,leave,d:array[0..maxn+1] of longint;//GetIn,GetOff两个数组分别表示每个景点上车与下车人数,right[i]表示i后第一个满足车等人(即车要浪费时间)的站点
     p,count,n,m,k,i,j,maxcnt,maxi,temp:longint;                          //D数组表示每一段路公交车走的时间,leave表示最早允许离开的时间,get为车到站的时间
 function max(x,y:longint):longint;//求出所给两数的大数函数
 begin
   if x>y then
     exit(x)
     else
      exit(y);
 end;
 function min(x,y:longint):longint;//求出两个数的小数函数
 begin
   if x<y then
     exit(x)
     else exit(y);
 end;
 BEGIN
  {assign(input,’bus.in’);
  assign(output,’bus.out’);
  reset(input);
  rewrite(output); }
 read(n,m,k);//读入景点个数、游客人数以及加速器的个数
 for i:=1 to n-1 do read(D[i]);//读入汽车每段路的花费时间
 for i:=1 to m do
   begin
   read(t[i],a[i],b[i]);//读入每个游客的上下站以及时间
   inc(GetOff[b[i]]);inc(GetIn[a[i]]);//记录景点的上下车情况
   leave[a[i]]:=max(leave[a[i]],t[i]);//汽车的出发时间为乘客到达时间与汽车现有状态下的出发时间两数中的大者,注意,因为有可能在使用加速器后路程所需时间为零,所以最早的时间不考虑汽车
   end;                                 的过程,所以说leave可以看做是汽车到站时间与人到站时间的取大值                                                                 
 for i:=2 to n do
   get[i]:=max(leave[i-1],get[i-1])+D[i-1];//到达景点的时间是出发时间、上一个景点的到达时间二者中的最大值,还要加上在路上花费的时间
 p:=1;
 for i:=1 to n do
   begin
   while((p<n)and(leave[p]<get[p]))or(p<=i)do inc(p);//leave[p]<get[p]可以寻找i后面第一个满足车等人的站点
   right[i]:=p;//给某个D[i]减一后会使后面连续的人等车的车站的乘客提前上车。直到一个车站leave[j]>get[j](车等人),人来的时间是不能跟改变的。所以提前了上车时间的旅客提前了的一分钟要            
   end;          在等人上浪费掉,所以旅行时间不会减小。也就是说令right[i]为i后面第一个满足车等人的站点。                  
 for i:=1 to n do
   s[i]:=s[i-1]+GetOff[i];//S表示在一个车站之前(包括此车站)下车人数的总和
 while k>0 do
   begin
   maxcnt:=0;
   for i:=1 to n-1 do//n个景点就有n-1次加速机会
     if (s[right[i]]-s[i]>maxcnt)and(D[i]>0)//大家可以想一想,好不容易提前的一分钟又被一个懒人浪费了,这种情况必然是会出现的,但我们怎么做可以才能减少浪费呢?对!让在等人的那一站下
       then begin                             车的人尽可能的多,则游客浪费在车上的时间就尽可能地少,以此方法,找出加速所起作用最大的一个车站
            maxcnt:=s[right[i]]-s[i];//记录并更新最大的下车人数
            maxi:=i;//记录下车站的门牌号                                          
            end;                     
   if maxcnt=0
     then break//如果没人下车,显然太亏,直接退出循环
     else begin
   {步骤1}temp:=maxlongint;j:=maxi+1;//temp用来记录这段过程所需要的加速器个数,j用来记录加速以后的车站
          while(j<n)and(leave[j]<get[j])do//这个循环可以确保从maxi到right[i]都要是人等车(尽可能让车等人的情况出现靠后,越后越好)
            begin                 //解释temp:因为你现在由上面过程已经确定,不管怎样,在right[j]站一定会有损耗,但你现在又加速了,损耗的车站就可能来的早了,比如说,你现在从A去D,知道
            temp:=min(get[j]-leave[j],temp);//从A到B你可以用3个加速器,但你又可以算出从B到C你最多可以用1个加速器,如果多了的话C站就会发生损耗,使车等人的情况提前,所以一定要减少损耗!
            inc(j);//枚举后面的每一个可以加速的路段,按照上述方法找出最节省的办法
            end;
          temp:=min(D[maxi],temp);//步骤2
          temp:=min(k,temp);//步骤3
          dec(k,temp);//相当于k:=k-temp,k使用后更新
          dec(D[maxi],temp);//路径所需时间更新                                                          每次加速都会考虑三种情况:
          for j:=maxi+1 to right[i] do                                                     (1).i+1到right[i]中最小的Get[j]-Leave[j]
            get[j]:=max(get[j-1],leave[j-1])+D[j-1];//get数组的更新                         (2).D[i]很小全部减掉(必须保证每个D[i]>=0)
          p:=maxi;count:=GetOff[maxi];                                                     (3).k很小全部用掉
          for j:=maxi to right[i]-1 do                                                      在上述三种情况中取最小值,左边的过程就是实现三种处理
            begin
              while((p<n)and(leave[p]<get[p]))or(p<=j)do inc(p);
              if p>=right[j] then break;
              right[j]:=p;//由于加速器的使用,right[i]也需要更新
            end;
          end;
   end;
 get[1]:=leave[1];get[n]:=max(get[n],leave[n]);//车到第n个景点的时间更新
 for i:=1 to m do
   inc(ans,get[b[i]]-t[i]);//相当于ans:=ans+get[b[i]]-t[i]
 writeln(ans);
 close(input);
  close(output);
 END.

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/189999.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号