Подсчитайте максимально возможное количество ничьих в матче между двумя людьми

Опубликовано: 20 Сентября, 2022

Дан массив пар v[][] размера N , который показывает оценку совпадения в N случаях, где (v[i][0], v[i][1]) показывает оценку, эквивалентную ( p, q ) из 2 игроков в этот момент. После забитого гола счет изменится на ( p+1: q ) или ( p: q+1 ). Задача состоит в том, чтобы найти максимальное количество ничьих за весь матч.

Примечание : последний счет обозначает окончательный результат матча. Счет предоставляется в порядке возрастания по мере увеличения времени.

Примеры:

Input: N = 3, v[][] = {{2, 0},  {3, 1}, {3, 4}}
Output: 2
Explanation: Possible scores in the match would be
0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4
Now,  0:0 and 3:3 are two scores leading to draw. 
Thus, answer = 2.

Input: N = 1, v[][] = {{5, 4}} 
Output: 5
Explanation: Possible scores in the match would be 
0:0, 0:1, 1:1, 1:2, 2:2, 2:3, 3:3, 3:4, 4:4, 5:4  
Now, 0:0, 1:1, 2:2, 3:3 and 4:4 are five scores leading to draw. 
Thus, answer = 5.

Подход: Предполагая оценку (p, q) и (r, s) . Вставьте между парами (x, x) как можно больше. Этот x должен быть таким, чтобы:
p ≤ x ≤ r и q ≤ x ≤ s , таким образом, max(p, q) ≤ x ≤ min(r, s). Итак, просто подсчитайте количество таких x . Выполните следующие шаги, чтобы решить проблему:

  • Инициализировать пары p1[] и p2[].
  • Инициализируйте переменные draws как 1 и diff как 0.
  • Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
    • Установите p2 как v[i].
    • Если p1.first совпадает с p1.second , тогда уменьшите значение розыгрышей на 1.
    • Установите разницу как min( p2.first , p2.second) – max(p1.first, p1.second) + 1.
    • Если diff больше 0 , увеличьте значение отрисовки на diff.
    • Установите значение p1 как p2.
  • После выполнения вышеуказанных шагов выведите значение draws в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:


Сложность времени: НА)
Вспомогательное пространство: О(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ