Скачать программы Все программы автора
АВТОБУС
Служебный автобус совершает один рейс по установленному маршруту и в случае наличия свободных мест подбирает рабочих, которые ожидают на остановках, и отвозит их на завод. Автобус также может ждать на остановке рабочих, которые еще не пришли. Известно время прихода каждого рабочего на свою остановку и время проезда автобуса от каждой остановки до следующей. Автобус приходит на первую остановку в нулевой момент времени. Продолжительность посадки рабочих в автобус считается нулевой.
Задание Написать программу BUS, которая определит минимальное время, за которое автобус привезет максимально возможное количество рабочих.
Входные данные Входной текстовый файл BUS.DAT в первой строке содержит количество остановок N и количество мест в автобусе M. Каждая i-я строчка из последующих N строчек содержит целое число — время движения от остановки і к остановке i+1 (N+1-я остановка — завод), количество рабочих K, которые придут на i-ю остановку, и время прихода каждого рабочего на эту остановку в порядке прихода (1£M£2000, 1£N,K£200000).
Пример входных данных.
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Выходные данные Единственная строка выходного текстового файла BUS.SOL должен содержать минимальное время, необходимое для перевозки максимального количества рабочих.
Пример выходных данных. 4
{$A-,B-,D-,E-,F-,G-,I+,L-,N-,O-,P-,Q-,R+,S+,T-,V-,X-}
{$M 16384,0,655360}
{$M 65384,0,655360}
program cybus;
const
maxStop = 200000;
maxPasag = 2000;
type
tarr = array [0..maxPasag+1] of longint;
var
i,q,num:longint;
alldist,n,max,dist,distold,s,numpeople:longint;
global,cur:tarr;
function min(a,b:longint):longint;
begin if a<b then min:=a else min:=b;end;
function mx(a,b:longint):longint;
begin if a>b then mx:=a else mx:=b;end;
procedure union(coef:longint;var a:tarr;var b:tarr);
var i,j,k,m:longint;
c:tarr;
begin
fillchar(c,sizeof(c),0);a[a[0]+1]:=maxLongint;b[b[0]+1]:=maxLongint-coef;
i:=1;j:=1;k:=0;
m:=min(a[0]+b[0],max);
while m>k do
begin
inc(k);
if (a[i]<b[j]+coef) then begin c[k]:=a[i];inc(i);end
else begin c[k]:=b[j]+coef;inc(j);end;
end;
c[0]:=m;
b:=c;
end;
begin
assign(input,'bus.dat');reset(input);
assign(output,'bus.sol');rewrite(output);
read(num,max);s:=0;
numpeople:=0;alldist:=0;
for q:=1 to num do
begin
fillchar(cur,sizeof(cur),0);
read(dist,n);inc(alldist,dist);inc(numpeople,n);inc(s,dist);cur[0]:=min(n,max);for i:=1 to cur[0] do read(cur[i]);readln;
if q=1 then global:=cur else union(distold,cur,global);
distold:=dist;
end;
writeln(mx(global[global[0]]+dist,s));
{ writeln('Peoples: ',numpeople);
writeln('MinTime: ',s);}
close(output);
end.