SHARE
TWEET

Untitled

a guest Dec 13th, 2019 83 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top