Due volte più grande#11286

Due volte più grande (Editoriale)

Chiameremo l'intervallo $A [i \dots j]$ A[i \ldots j] buono, se tutti i suoi elementi appartengono all'intervallo $[A_{i}; 2 \cdot A_{i}]$ [A_i; 2 \cdot A_i]. Poiché l'array è ordinato, per questo è sufficiente che sia soddisfatta la condizione $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i.

Manterremo i puntatori $i$ e $j$ in modo che $j$ punti al primo elemento che non rientra nel segmento buono che inizia in $i$ . In altre parole, il segmento $[i \dots j - 1]$ [i \ldots j - 1] è buono, mentre il segmento $[i \dots j]$ [i \ldots j] è cattivo.

Ad esempio, per la seguente sequenza

gli intervalli $[2; 2], [2; 3], [2; 4]$ [2; 2], [2; 3], [2; 4] e $[2; 5]$ sono buoni.
gli intervalli $[2; 6], [2; 7]$ [2; 6], [2; 7] sono cattivi.

Ad ogni passo eseguiamo una delle due azioni:

se $j$ non è uscito dai limiti dell'array e $A_{j} \leq 2 \cdot А_{i}$ A_j \le 2 \cdot А_i, espandiamo la finestra: aumentiamo $j$ di $1$ ;
altrimenti la finestra per l'attuale $i$ è massima: stampiamo la risposta $j - i$ j - i e spostiamo il confine sinistro, aumentando $i$ di $1$ .

Ognuno dei puntatori solo aumenta e percorre l'array al più una volta, pertanto la complessità temporale dell'algoritmo è $O (n)$ .

Esempio

Consideriamo il movimento dei puntatori per l'esempio riportato.

Per lo stato dato $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i, quindi spostiamo in avanti il puntatore $j$ .

Ora $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i. Dovremmo spostare in avanti il puntatore $i$ . Tuttavia, prima di spostarlo, stampiamo il numero di elementi compresi tra $A_{i}$ A_i e $2 \cdot A_{i}$ 2 \cdot A_i inclusi. Esso è pari a $j - i = 6 - 2 = 4$ j - i = 6 - 2 = 4.

Spostiamo $j$ in avanti finché $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i.

Ora $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i. Stampiamo la risposta per $i = 3$ i = 3 (essa è pari a $j - i = 8 - 3 = 5$ j - i = 8 - 3 = 5) e aumentiamo $i$ di $1$ .

Implementazione dell'algoritmo

Leggiamo i dati in ingresso.

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

Inizializziamo i puntatori $i = j = 0$ i = j = 0.

i = j = 0;

Spostiamo i puntatori in avanti finché per ogni valore $i < n$ i < n non sarà trovata la risposta.

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

Se $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i (ma a condizione che $j$ non sia uscito dai limiti dell'array, cioè $j < n$ j < n), allora espandiamo l'intervallo corrente, aumentando il puntatore $j$ .

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

Quando $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i stampiamo la risposta per l'indice $i$ e aumentiamo $i$ di uno.

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

Implementazione dell'algoritmo — ricerca binaria, O(n log n)

Leggiamo i dati in ingresso.

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

Per ogni indice $i < n$ i < n tramite la ricerca binaria cerchiamo il valore massimo dell'indice $x$ tale che nell'intervallo $[i; x - 1]$ [i; x - 1] si trovino i numeri da $A_{i}$ A_i a $2 \cdot A_{i}$ 2 \cdot A_i, mentre $A_{x} > 2 \cdot A_{i}$ A_x > 2 \cdot A_i. Il numero di numeri nell'intervallo $[i; x - 1]$ [i; x - 1] è pari a $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);
}

Implementazione 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

Implementazione Python

Leggiamo i dati in ingresso.

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

Inizializziamo i puntatori $i = j = 0$ i = j = 0.

i = j = 0

Spostiamo i puntatori in avanti finché per ogni valore $i < n$ i < n non sarà trovata la risposta.

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

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

Quando $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i stampiamo la risposta per l'indice $i$ e aumentiamo $i$ di uno.

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

Implementazione Python — ricerca binaria, O(n log n)

from bisect import bisect_right

Leggiamo i dati in ingresso.

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

Per ogni indice $i < n$ i < n tramite la ricerca binaria cerchiamo il valore massimo dell'indice $x$ tale che nell'intervallo $[i; x - 1]$ [i; x - 1] si trovino i numeri da $А_{i}$ А_i a $2 \cdot A_{i}$ 2 \cdot A_i, mentre $A_{x} > 2 \cdot A_{i}$ A_x > 2 \cdot A_i. Il numero di numeri nell'intervallo $[i; x - 1]$ [i; x - 1] è pari a $x - i$ x - i.

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