Guest User

Untitled

a guest
Dec 13th, 2019
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 6. {\bf Подотрезок с заданной суммой}\\
  2.  
  3.    \textit{SOLUTION}\\
  4.    Воспользуемся методом двух указателей. \\
  5. Для каждого left ищем первое $ right : \sum a_{left} ... a_{right} \ge S $
  6. Если получившаяся сумма нам подходит, то победа. Если нет, то сдвигаем левую границу и для нее ищем новую right.
  7. Ниже привожу примерный код для реализации идеи.
  8. \begin{code}
  9.    int sum = 0;
  10.    int right = 0;
  11.    for (int left = 0; left < n; left++) {
  12.        while (sum < S)
  13.            sum += array[right++];
  14.        if (sum == S)
  15.            pobeda;
  16.        sum -= array[left];
  17.    }
  18. \end{code}
  19.  
  20.    \textit{Соображения насчет корректности}\\
  21.    Пусть S представим в виде суммы нескольких последовательных элементов в массиве, то есть $ \exists left,right : \sum a_{left} ... a_{right} = S$\\
  22. По алгоритму мы перебираем все left, поэтому дойдем и до left из ответа. \\
  23. Для этого конкретного left по алгоритму мы найдем и первый right: $ \sum a_{left} ... a_{right} \ge S $ \\
  24. Таким образом, какими бы ни былы left, right из ответа, по алгоритму мы их найдем.
RAW Paste Data