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)


相关推荐

  • 优化算法——梯度下降法

    优化算法——梯度下降法最近一直在看机器学习的材料,归纳起来就是把一个学习的问题转化为优化的问题,机器学习算法的本质就是如何对问题抽象建模,使一个学习的问题变为一个优化的问题。优化的算法有很多种,从最基本的梯度下降法到现在的一些启发式算法,如遗传算法(GA),差分演化算法(DE),粒子群算法(PSO)和人工蜂群算法(ABC)。梯度下降法又被称为最速下降法(Steepestdescendmethod),其理论基

    2022年10月27日
  • zookeeper入门教程_dubbo和Zookeeper详解

    zookeeper入门教程_dubbo和Zookeeper详解zookeeperwatcher架构zookeeper 配置中心分布式ID分布式锁集群搭建数据一致性协议:zab协议Zookeeper Leader选举Observer角色及其配置watcher架构客户端首先将Watcher注册到服务器,同时将Watch对象保存到客户端的Watch管理器中。当Zookeeper服务器监听到的数据发生变化时,服务器会通知客户端,接着客户端的Watch管理器会触发相关的Watcher来回调响应处理逻辑,从而完成整体的数据发布/订阅流程。javaAPIJava

  • JSP的Web监听器(Listener)

    JSP的Web监听器(Listener)JSP的Web监听器(Listener)

  • JDK卸载删除

    JDK卸载删除Java卸载1.进入环境变量,点击Java_Home2.进入路径,删除JDK清理环境变量删除path下关于Java的环境变量查看是否清除cdm运行输入java-version

  • C语言中数组的总结

    C语言中数组的总结目录一维数组的创建和初始化一维数组的使用一维数组在内存中的存储指针的初步介绍一维数组的指针访问二维数组的创建和初始化二维数组的使用二维数组在内存中的存储二维数组的指针访问有关数组的运算数组作为函数参数1.一维数组的创建和初始化数组的创建:在创建数组时,我们必须定义数组的类型和大小,数组的大小不能为0,数组中的元素类型都是相同的。eg:intarr[

  • 微软输入法打不了拼音_微软拼音输入法怎么用

    微软输入法打不了拼音_微软拼音输入法怎么用
    尽管已经来到了2010版本,依然无法快速地输入各种特殊符号。
    谁会愿意为了输入一个黑方框“■”,让自己繁忙的手离开键盘,
    让自己疲劳的眼神聚焦到输入条→一路猛击软键盘→特殊符号→选择→关闭软键盘呢?
     
    而如果你使用搜狗或其它同一时代(注意注意同一时代)的拼音输入法,
    完全没有这个烦恼,你只需要轻敲fk,出来的备选里再敲某个数字键就完成了。
     
    这么多年了,微软依然不懂得中国人需要一个什么样的拼音输入法,
    哪怕它可能

发表回复

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

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