Версия для печати темы

Автор: Виликан 4.10.2011 20:57

4. Морской бой. Параллельно береговой линии в море стоит вражеский флот. Полоса, в которой расположен флот, условно разбита на N квадратов. На главном корабле нашего флота находится секретное орудие, которое может нанести удар сразу по k смежным (т.е. подряд идущим) квадратам. Все вражеские корабли, находящиеся в пораженных квадратах будут уничтожены. К сожалению, у секретного орудия есть всего один заряд, поэтому требуется всего одним выстрелом нанести максимальный урон противнику.
Задание. Напишите программу battle, определяющую максимальное количество кораблей, которое может быть уничтожено одним выстрелом.
Входные данные. В первой строке записаны два целых числа N и k (1<=k<=N< 100000). Во второй строке задаются N целых чисел Ai, каждое из которых определяет количество кораблей в соответствующем квадрате полосы (0 < Ai < 10000).
Выходные данные. В единственной строке выведите наибольшее количество кораблей, которые могут быть уничтожены.
Примеры входных и выходных данных

ввод вывод
7 3 . 1
3212321 .



Добавлено через 1 мин.
если кому лень писать решение, то хоть натолкните на мысль... пожалуйста

Автор: Lapp 5.10.2011 7:41

Дело не в лени )). Помочь можно, не хочется писать все за тебя.

А какая тут может быть "идея"? Тут все прозрачно..
Сначала считаешь сумму s по первым k квадратам, также присваиваешь ее переменной max. Потом делаешь цикл от i=k+1 до n - вычитаешь из s содержимое i-k квадрата и прибавляешь содержимое i квадрата. Если s больше max, то кладешь s в max. Вот и все.

Автор: Виликан 5.10.2011 21:19

Спасибо большое! Ну для вас это конечно просто и понятно, но мне, человеку который в сумме месяца 3 учит паскаль это не всегда "прозрачно"...
Еще раз спасибо.

Автор: Lapp 6.10.2011 1:04

Нет проблем, заходи еще. Если ты не за готовым решением приходишь - мы поможем.
По сути, то, что я написал выше, годится не только для Паскаля - это алгоритм. На всякий случай пишу то же самое на Паскале - проверь себя:

  s:= 0;
  for i:=1 to k do s:= s+a[i];
  max:= s;
  for i:= k+1 to n do begin
    s:= s - a[i-k] + a[i];
    if s>max then max:=s
  end;