of array – a sequence of one or more
consecutive elements in array.D-good segment – segment, in which sum of elements not greater than D.
Count the pairs (L, R) such that segment [L, R] of array A is D-good.
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Two pointers method
Содержание
- 2. ProblemThere is array A with N positive
- 3. 1. Very primitive solutionSum elements for each
- 4. 2. Primitive solutionNotice that sum(L, R) =
- 5. 3. Good solutionNotice that it’s enough to
- 6. 3. Good solutionprefixSum[0] = a[0];for (int i
- 7. 4. Best solutionNotice that maxR(L)>=maxR(L-1). So we
- 8. Tracing, step 0Left=0Right=-1ANS=0SUM=0D=6
- 9. Tracing, step 1Left=0Right=0ANS=0SUM=1D=6
- 10. Tracing, step 2Left=0Right=1ANS=0SUM=3D=6
- 11. Tracing, step 3Left=0Right=2ANS=0SUM=6D=6
- 12. Tracing, step 4Left=0Right=2ANS=3SUM=6D=6
- 13. Tracing, step 5Left=1Right=2ANS=3SUM=5D=6
- 14. Tracing, step 6Left=1Right=2ANS=5SUM=5D=6
- 15. Tracing, step 7Left=2Right=2ANS=5SUM=3D=6
- 16. Tracing, step 8Left=2Right=3ANS=5SUM=6D=6
- 17. Tracing, step 9Left=2Right=3ANS=7SUM=6D=6
- 18. Tracing, step 10Left=3Right=3ANS=7SUM=3D=6
- 19. Tracing, step 11Left=3Right=3ANS=8SUM=3D=6
- 20. Tracing, step 12Left=4Right=3ANS=8SUM=0D=6
- 21. Tracing, step 13Left=5Right=3ANS=8SUM=-7D=6
- 22. Tracing, step 14Left=5Right=4ANS=8SUM=0D=6
- 23. Tracing, step 15Left=6Right=4ANS=8SUM=-8D=6
- 24. Tracing, step 16Left=6Right=5ANS=8SUM=0D=6
- 25. Tracing, step 17Left=6Right=6ANS=8SUM=6D=6
- 26. Tracing, step 18Left=6Right=6ANS=9SUM=6D=6
- 27. Tracing, step 19Left=7Right=6ANS=9SUM=0D=6
- 28. Tracing, step 20Left=7Right=7ANS=9SUM=4D=6
- 29. Tracing, step 21Left=7Right=8ANS=9SUM=6D=6
- 30. Tracing, step 22Left=7Right=8ANS=11SUM=6D=6
- 31. Tracing, step 23Left=8Right=8ANS=11SUM=2D=6
- 32. Tracing, step 24Left=8Right=9ANS=11SUM=5D=6
- 33. Tracing, step 25Left=8Right=9ANS=13SUM=5D=6
- 34. Tracing, step 26Left=9Right=9ANS=13SUM=3D=6
- 35. Tracing, step 27Left=9Right=9ANS=14SUM=3D=6
- 36. Tracing, step 28Left=9Right=9ANS=14SUM=0D=6
- 37. Other examplesThere are 2 sorted arrays of
- 38. Скачать презентацию
- 39. Похожие презентации
ProblemThere is array A with N positive integers.Segment of array – a sequence of one or more consecutive elements in array.D-good segment – segment, in which sum of elements not greater than D.Count the pairs (L,
![2. Primitive solutionNotice that sum(L, R) = sum(L, R-1)+A[R]If sum(L, R1)>D then](/img/tmb/15/1459735/5dc10f0c11bc12b0a3522670226c281c-720x.jpg "Two pointers method")
![3. Good solutionprefixSum[0] = a[0];for (int i = 1; i < n;](/img/tmb/15/1459735/033580dbc1e6f8f43d1910ebd7672db7-720x.jpg "Two pointers method")
Слайд 2
Problem
There is array A with N positive integers.
Segment
D-good segment – segment, in which sum of elements not greater than D.
Count the pairs (L, R) such that segment [L, R] of array A is D-good.
Слайд 3
1. Very primitive solution
Sum elements for each pair
(L, R).
for (int i = 0; i < n;
++i)for (int j = i; j < n; ++j)
{
int sum = 0;
for (int k = i; k <= j; ++k)
sum += a[k];
if (sum <= d)
ans++;
}
O(N3)
Слайд 4
2. Primitive solution
Notice that sum(L, R) = sum(L,
R-1)+A[R]
If sum(L, R1)>D then sum(L, R2)>D for each R2>R1
for
(int i = 0; i < n; ++i){
int sum = 0;
for (int j = i; j < n; ++j)
{
sum += a[j];
if (sum <= d) ans++;
else break;
}
}
O(N2)
Слайд 5
3. Good solution
Notice that it’s enough to find
maxR(L) = max(R) such sum(L, R)D
for each R’>R.We can precompute prefix sums and than find maxR by binary search.
Слайд 6
3. Good solution
prefixSum[0] = a[0];
for (int i =
1; i < n; ++i)
prefixSum[i] = prefixSum[i - 1]
+ a[i];for (int i = 0; i < n; ++i)
{
if (a[i] > d) continue;
int l = i, r = n;
while(r-l>1)
{
int mid = (l + r) / 2;
if (prefixSum[mid] - prefixSum[i] + a[i] <= d)
l = mid;
else
r = mid;
}
ans += l - i + 1;
}
O(NlogN)
Слайд 7
4. Best solution
Notice that maxR(L)>=maxR(L-1). So we can
start finding maxR(L) from maxR(L-1).
In this way out pointer
R goes only forward.int right = -1;
int sum = 0;
for (int i = 0; i < n; ++i)
{
while (right + 1 < n && sum + a[right + 1] <= d)
sum += a[++right];
ans += right - i + 1;
sum -= a[i];
}
O(N)
Слайд 37
Other examples
There are 2 sorted arrays of integers:
A and B. Count pairs (i, j) such that
A[i]=B[j].There are N points on circle. Find two points such that distance between them is maximal.
There are N points on circle. Find three points such that area of triangle is maximal.
