Rambler's Top100

Скачать программы    Все программы автора

АВТОБУС

Служебный автобус совершает один рейс по установленному маршруту и в случае наличия свободных мест подбирает рабочих, которые ожидают на остановках, и отвозит их на завод. Автобус также может ждать на остановке рабочих, которые еще не пришли. Известно время прихода каждого рабочего на свою остановку и время проезда автобуса от каждой остановки до следующей. Автобус приходит на первую остановку в нулевой момент времени. Продолжительность посадки рабочих в автобус считается нулевой.

Задание Написать программу 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.

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ
Hosted by uCoz