Сбор-черники. Решение состоит в том, чтоб последовательно перебрать первый куст из тех, что мы берем, посчитать сумму количества ягод на нем и следующих двух. Из таких сумм необходимо найти максимум
 Скачать 33.5 Kb.
|
|
Сбор черники (Время: 1 сек. Память: 16 Мб Сложность: 17%) В фермерском хозяйстве в Карелии выращивают чернику. Она растет на круглой грядке, причем кусты высажены только по окружности. Таким образом, у каждого куста есть ровно два соседних. Всего на грядке растет N кустов. Эти кусты обладают разной урожайностью, поэтому ко времени сбора на них выросло различное число ягод – на i-ом кусте выросло ai ягод. В этом фермерском хозяйстве внедрена система автоматического сбора черники. Эта система состоит из управляющего модуля и нескольких собирающих модулей. Собирающий модуль за один заход, находясь непосредственно перед некоторым кустом, собирает ягоды с этого куста и с двух соседних с ним. Напишите программу для нахождения максимального числа ягод, которое может собрать за один заход собирающий модуль, находясь перед некоторым кустом заданной во входном файле грядки. Входные данные Первая строка входного файла INPUT.TXT содержит целое число N (3 <= N <= 1000) – количество кустов черники. Вторая строка содержит N целых положительных чисел a1, a2, ..., aN – число ягод черники, растущее на соответствующем кусте. Все ai не превосходят 1000. Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу.  Рекомендации В этой задаче необходимо найти три рядом расположенных куста таких, что сумма количества ягод на них максимальна. При этом необходимо учитывать то, что грядка круглая, и поэтому можно взять, например, последний и два первых куста. Заметим также, что число ягод невелико и для его хранения можно использовать 32-битный целочисленный тип данных (longint в языке Pascal, int в языках C и Java). Решение состоит в том, чтоб последовательно перебрать первый куст из тех, что мы берем, посчитать сумму количества ягод на нем и следующих двух. Из таких сумм необходимо найти максимум. Этот алгоритм работает за линейное от n время. Один из способов обрабатывать то, что грядка является круглой, использовать массив длиной n+2 и в последние два элемента записать первые два. Program da; type mass=array[0..1002] of longint; var f,h:text; m:mass; max,min,a,l,q,b,i,k,n:longint; Begin assign(f,'input.txt'); assign(h,'output.txt'); reset(f); rewrite(h); readln(f,n); read(f,m[1+n]); m[1]:=m[1+n]; read(f,m[2+n]); m[2]:=m[2+n]; for i:=3 to n do read(f,m[i]); max:=m[1]+m[2]+m[3]; for i:=2 to n+1 do Begin if m[i]+m[i-1]+m[i+1]>max then max:=m[i]+m[i-1]+m[i+1]; end; writeln(h,max); close(f); close(h); end. |