Удвічі більше#11286

Удвічі більше (Розбір)

Інтервал $A [i \dots j]$ A[i \ldots j] будемо називати хорошим, якщо всі його елементи належать проміжку $[A_{i}; 2 \cdot A_{i}]$ [A_i; 2 \cdot A_i]. Оскільки масив відсортований, для цього достатньо виконання умови $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i.

Будемо підтримувати вказівники $i$ та $j$ так, щоб $j$ вказував на перший елемент, що не входить у хороший відрізок з початком у $i$ . Іншими словами, відрізок $[i \dots j - 1]$ [i \ldots j - 1] хороший, а відрізок $[i \dots j]$ [i \ldots j] поганий.

Наприклад, для наступної послідовності

інтервали $[2; 2], [2; 3], [2; 4]$ [2; 2], [2; 3], [2; 4] та $[2; 5]$ є хорошими.
інтервали $[2; 6], [2; 7]$ [2; 6], [2; 7] є поганими.

На кожному кроці виконуємо одну з двох дій:

якщо $j$ не вийшов за межі масиву і $A_{j} \leq 2 \cdot А_{i}$ A_j \le 2 \cdot А_i, розширюємо вікно: збільшуємо $j$ на $1$ ;
інакше вікно для поточного $i$ максимальне: виводимо відповідь $j - i$ j - i і зсуваємо ліву межу, збільшуючи $i$ на $1$ .

Кожен із вказівників лише збільшується і проходить масив не більше одного разу, тому часова складність алгоритму становить $O (n)$ .

Приклад

Розглянемо рух вказівників для наведеного прикладу.

Для заданого стану $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i, тому рухаємо вперед вказівник $j$ .

Тепер $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i. Вперед слід рухати вказівник $i$ . Однак перед його переміщенням виводимо кількість елементів, що лежать між $A_{i}$ A_i та $2 \cdot A_{i}$ 2 \cdot A_i включно. Вона дорівнює $j - i = 6 - 2 = 4$ j - i = 6 - 2 = 4.

Рухаємо $j$ вперед, поки $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i.

Тепер $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i. Виводимо відповідь для $i = 3$ i = 3 (вона дорівнює $j - i = 8 - 3 = 5$ j - i = 8 - 3 = 5) і збільшуємо $i$ на $1$ .

Реалізація алгоритму

Читаємо вхідні дані.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Ініціалізуємо вказівники $i = j = 0$ i = j = 0.

i = j = 0;

Рухаємо вказівники вперед, поки для кожного значення $i < n$ i < n не буде знайдена відповідь.

while (i < n) // [i..j]
{

Якщо $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i (але при цьому $j$ не вийшло за межі масиву, тобто $j < n$ j < n), то розширюємо поточний інтервал, збільшуючи вказівник $j$ .

  if ((j < n) && (a[j] <= 2 * a[i])) j++;
  else
  {

При $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i виводимо відповідь для індексу $i$ та збільшуємо $i$ на одиницю.

    printf("%d ", j - i);
    i++;
  }
}

Реалізація алгоритму — бінарний пошук, O(n log n)

Читаємо вхідні дані.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Для кожного індексу $i < n$ i < n за допомогою бінарного пошуку шукаємо таке найбільше значення індексу $x$ , що на інтервалі $[i; x - 1]$ [i; x - 1] знаходяться числа від $A_{i}$ A_i до $2 \cdot A_{i}$ 2 \cdot A_i, а $A_{x} > 2 \cdot A_{i}$ A_x > 2 \cdot A_i. Кількість чисел на інтервалі $[i; x - 1]$ [i; x - 1] дорівнює $x - i$ x - i.

for (i = 0; i < n; i++)
{
  x = upper_bound(v.begin(), v.end(), 2 * v[i]) - v.begin();
  printf("%d ", x - i);
}

Java реалізація

import java.util.*;
 
public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m[] = new int[n];
    for(int i = 0; i < n; i++)
      m[i] = con.nextInt();

    int i = 0, j = 0;
    while (i < n) // [i..j]
    {
      if ((j < n) && (m[j] <= 2 * m[i])) j++;
      else
      {
        System.out.print(j - i + " ");
        i++;
      }
    }

    con.close();
  }
}

Java

Python реалізація

Читаємо вхідні дані.

n = int(input())
lst = list(map(int,input().split()))

Ініціалізуємо вказівники $i = j = 0$ i = j = 0.

i = j = 0

Рухаємо вказівники вперед, поки для кожного значення $i < n$ i < n не буде знайдена відповідь.

while (i < n): # [i..j]

  if (j < n and lst[j] <= 2 * lst[i]):
    j += 1
  else:

При $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i виводимо відповідь для індексу $i$ та збільшуємо $i$ на одиницю.

    print(j - i, end=" ");
    i += 1

Python реалізація — бінарний пошук, O(n log n)

from bisect import bisect_right

Читаємо вхідні дані.

n = int(input())
v = list(map(int, input().split()))

Для кожного індексу $i < n$ i < n за допомогою бінарного пошуку шукаємо таке найбільше значення індексу $x$ , що на інтервалі $[i; x - 1]$ [i; x - 1] знаходяться числа від $А_{i}$ А_i до $2 \cdot A_{i}$ 2 \cdot A_i, а $A_{x} > 2 \cdot A_{i}$ A_x > 2 \cdot A_i. Кількість чисел на інтервалі $[i; x - 1]$ [i; x - 1] дорівнює $x - i$ x - i.

for i in range(n):
  x = bisect_right(v, 2 * v[i])
  print(x - i, end=" ")