Дано n целых чисел a1, a2, ..., an и k. Сколько подмассивов длиной k, что эти элементы могут построить треугольник?

Question

Учитывая набор различных положительных целых чисел, скажем, что он может «построить треугольник», если он может быть разбит на три подмножества, суммы которых могут быть длинами трех сторон треугольника (то есть: три подмножества, чьи суммы удовлетворяют неравенству треугольника ). Например, {1, 2, 3, 4} может «построить треугольник», разбив его на {{1, 2}, 3, 4}, потому что треугольник может иметь длины сторон 1 + 2, 3 и 4 (потому что 1 + 2 + 3> 4, 1 + 2 + 4> 3 и 3 + 4> 1 + 2).

Мне дан массив A до 10 ⁵ различные неотрицательные целые числа в диапазоне [0, 10 ⁹ ] и целое число k , и мне нужно найти, сколько смежных подмассивы длиной k могут строить треугольники. Например, если A = [1, 3, 4, 2, 5, 9] и k = 3, то существует два таких подмассива: [3, 4, 2] и [4, 2, 5].

Я пробовал следующий подход:

• Итерация по A , проверка каждого смежного подмассива длины к .
  • Для каждого такого подмассива найдите каждый его раздел на три подмножества.
    • Для каждого такого разбиения вычислите суммы трех подмножеств и проверьте, удовлетворяют ли они неравенству треугольника.
• Возвращает число подмассивы, где проверка прошла хотя бы для одного раздела.

Это дает правильный ответ, но требует O (3 ^k n ) время, где n - длина A .

. Я читал об алгоритме O ( n ) для этого проблема, но я не понимаю, почему это работает:

• Итерировать по A , проверяя каждый смежный подмассив длины k .
  • Для каждого такого подмассива определите его сумму S и его наибольший элемент a _G , затем проверьте, если S > 2a _G .
    • Примечание # 1: Подмассив может построить треугольник тогда и только тогда, когда это так.
    • Примечание # 2: суммы всех подмассивов могут быть определены в O ( n ) время с использованием префиксных сумм.
    • Примечание # 3: наибольшие элементы всех подмассивов можно определить за время O ( n ) с помощью deque.
• Возвращает количество подмассивов, где проверка прошла хотя бы для одного раздела.

Мне было дано это объяснение для примечания № 1:

• Пусть i будет первым индексом подмассива, а j будет его последним индексом (таким, что j = i + k - 1).
• Представьте, что мы отсортировали элементы подмассива, так что A _i <<em> A _{i + 1} <… <<em> A _j .
• Представьте себе разбиение подмассива следующим образом:
  • x = A _i + A _{i + 2} +… + A _{j - 2}
  • y = A _{i + 1} + A _{i + 3} +… + A _{j −1}
  • z = A _j
• Легко доказать, что y + z> x и x + z> y; поэтому, чтобы проверить, удовлетворяет ли оно неравенству треугольника, остается только проверить, x + y> z, что эквивалентно проверке, если x + y + z> 2z.
• Но мы можем проверить это на самом деле сортировка: x + y + z - сумма всего подмассива, а z - его наибольший элемент.

То, что я не понимаю, - это объяснение показывает, что если мы разделим подмассив в Если указать c, то это разбиение удовлетворяет равенству треугольника тогда и только тогда, когда x + y + z> 2z. Но что, если мы разделим подмассив другим способом? Даже если этот раздел не удовлетворяет неравенству треугольника, не может ли быть другой, который это делает?

Answer 1

Неравенство треугольника можно переформулировать как (см. https://en.wikipedia.org/wiki/Triangle_inequality#Mathematical_expression_of_the_constraint_on_the_sides_of_a_triangle)

x+y+z > 2 max(x,y,z)

Для любого выбора разбиения для x, y и z мы имеем max(x,y,z) >= A_j. Таким образом, если разделение вы описали

x = A _i + A _{i + 2} +… + A _{j − 2}

y = A _{i + 1} + A _{i + 3} +… + A _{j − 1}

z = A _j

не удовлетворяет неравенству (т. Е. x+y+z > 2A_j не выполняется), тогда любое другое разбиение также не удовлетворит его.