Сорняки, задача из олимпиады.

@Vital_B · Регистрация: 20.10.2020

Author24 — интернет-сервис помощи студентам

Есть некое количество сорняков - n, расположенных в один ряд слева направо. Размер i-ого сорняка составляет h_i см. Человек может вырвать только k любых подряд идущих сорняков. Нужно найти, откуда начать, чтобы избавиться от сорняков с наибольшим суммарным размером.
Формат входных данных
В первой строке данных содержатся целые числа n и k - общее число сорняков на огороде и количество сорняков, которое человек может выполоть. Вторая строка содержит последовательность целых чисел h₁, h₂, ..., h_n, где h_1-n - размер сорняка.
Формат выходных данных
Выведите такое j, что сумма размеров k подряд идущих сорняков, начиная с j-ого, максимально возможная. Если таких j несколько, то выведите любое из них.
Примеры
Ввод Вывод
7 3 5
3 1 4 1 5 9 2

5 2 1
100 1 100 1 100

В первом случае сумма размеров сорняков, начиная с пятого, равна 5+9+2=16 - максимально возможная, поэтому ответ 5.
Во втором примере верным ответом также является любое число от 2 до 4.

@JuriiMW · 20.10.2020, 10:08

Pascal

type tt=class h:Integer;x:tt;end;
begin
  var(n,k):=ReadInteger2;var u:=new tt;u.h:=ReadInteger;var s:=u.h;var f:=u;for
  var i:=2 to k do begin u.x:=new tt;u:=u.x;Read(u.h);s+=u.h;end;u.x:=f;var(sm,
  si):=(s,1);for var i:=k+1 to n do begin u:=u.x;s-=u.h;u.h:=ReadInteger;s+=u.h;
  if sm<s then(sm,si):=(s,i-k+1);end;si.Print;
end.

Добавлено через 1 минуту
Почти как в классическом паскале решение получилось ;–)

P.S. Уважаемые модераторы, убедительно прошу, не исправлять и не форматировать код!

@eaa · 20.10.2020, 11:10

Pascal

begin
  var (n, k) := ReadInteger2;
  var h := ReadArrInteger(n);
  Range(1, n - k + 1).MaxBy(i -> h[i - 1:i - 1 + k].Sum).Print
end.

@JuriiMW · 20.10.2020, 11:23

eaa, ТС забыл сказать какие действуют ограничения на память…
А то, при больших n, думаю будет затратно по памяти и времени всё в память пихать, а потом ещё и нарезку из k отрезков делать.

@eaa · 20.10.2020, 11:57

Не по теме:

Сообщение от JuriiMW

ТС забыл сказать какие действуют ограничения на память

Не думаю что ему это интересно.

@Vital_B 0 / 0 / 0 Регистрация: 20.10.2020 Сообщений: 2
		1
	Сорняки, задача из олимпиады. 20.10.2020, 08:06. Показов 1205. Ответов 4 Метки задача, олимпиада, паскаль (Все метки) Есть некое количество сорняков - n, расположенных в один ряд слева направо. Размер i-ого сорняка составляет h_i см. Человек может вырвать только k любых подряд идущих сорняков. Нужно найти, откуда начать, чтобы избавиться от сорняков с наибольшим суммарным размером. Формат входных данных В первой строке данных содержатся целые числа n и k - общее число сорняков на огороде и количество сорняков, которое человек может выполоть. Вторая строка содержит последовательность целых чисел h₁, h₂, ..., h_n, где h_1-n - размер сорняка. Формат выходных данных Выведите такое j, что сумма размеров k подряд идущих сорняков, начиная с j-ого, максимально возможная. Если таких j несколько, то выведите любое из них. Примеры Ввод Вывод 7 3 5 3 1 4 1 5 9 2 5 2 1 100 1 100 1 100 В первом случае сумма размеров сорняков, начиная с пятого, равна 5+9+2=16 - максимально возможная, поэтому ответ 5. Во втором примере верным ответом также является любое число от 2 до 4. 0

@JuriiMW 5079 / 2651 / 2349 Регистрация: 10.12.2014 Сообщений: 10,028
	20.10.2020, 11:23	4
	eaa, ТС забыл сказать какие действуют ограничения на память… А то, при больших n, думаю будет затратно по памяти и времени всё в память пихать, а потом ещё и нарезку из k отрезков делать. 0

@eaa
	20.10.2020, 11:57 Сорняки, задача из олимпиады. #5
	Не по теме: Сообщение от JuriiMW ТС забыл сказать какие действуют ограничения на память Не думаю что ему это интересно. 0