NOIP2011观光公交

大家好，欢迎来到IT知识分享网。

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.