İki dəfə çox#11286

İki dəfə çox (Həll təhlili)

Əgər $A [i \dots j]$ A[i \ldots j] intervalının bütün elementləri $[A_{i}; 2 \cdot A_{i}]$ [A_i; 2 \cdot A_i] aralığında yerləşirsə, biz bu intervalı yaxşı adlandırırıq. Massiv sıralandığı üçün $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i şərtinin ödənilməsi kifayətdir.

Biz iki göstərici $i$ və $j$ saxlayırıq, belə ki $j$ göstəricisi $i$ -dən başlayan yaxşı intervala aid olmayan ilk elementi göstərir. Başqa sözlə, $[i \dots j - 1]$ [i \ldots j - 1] intervalı yaxşıdır, $[i \dots j]$ [i \ldots j] intervalı isə pisdir.

Misal üçün, aşağıdakı ardıcıllıq üçün:

$[2; 2], [2; 3], [2; 4]$ [2; 2], [2; 3], [2; 4] və $[2; 5]$ intervalları yaxşıdır.
$[2; 6], [2; 7]$ [2; 6], [2; 7] intervalları pisdir.

Hər addımda biz aşağıdakı iki əməldən birini yerinə yetiririk:

əgər $j$ massivin hüdudları daxilindədirsə və $A_{j} \leq 2 \cdot А_{i}$ A_j \le 2 \cdot А_i şərti ödənilirsə, pəncərəni genişləndirmək üçün $j$ -ni $1$ artırırıq;
əks halda, cari $i$ üçün pəncərə maksimaldır: $j - i$ j - i cavabını çap edirik və sol sərhədi $1$ artıraraq $i$ -ni dəyişdiririk.

Hər göstərici yalnız irəli hərəkət edir və massivi ən çoxu bir dəfə gəzir, ona görə də alqoritmin zaman mürəkkəbliyi $O (n)$ -dir.

Misal

Verilmiş misal üçün göstəricilərin hərəkətinə baxaq.

Verilmiş şərt üçün $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i, ona görə də $j$ göstəricisini irəli aparırıq.

İndi $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i. $i$ göstəricisini irəli aparmalıyıq. Lakin, bunu etməzdən əvvəl, $A_{i}$ A_i və $2 \cdot A_{i}$ 2 \cdot A_i arasında (daxil olmaqla) yerləşən elementlərin sayını çap edirik. O, $j - i = 6 - 2 = 4$ j - i = 6 - 2 = 4-ə bərabərdir.

$A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i olana qədər $j$ -ni irəli aparırıq.

İndi $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i. $i = 3$ i = 3 üçün cavabı çap edirik (o, $j - i = 8 - 3 = 5$ j - i = 8 - 3 = 5-ə bərabərdir) və $i$ -ni $1$ artırırıq.

Alqoritmin realizasiyası

Giriş məlumatlarını oxuyuruq.

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

$i = j = 0$ i = j = 0 göstəricilərini ilkinləşdiririk.

i = j = 0;

Hər $i < n$ i < n qiyməti üçün cavab tapılana qədər göstəriciləri irəli aparırıq.

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

Əgər $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i (və $j$ massivin hüdudlarını aşmayıbsa, yəni $j < n$ j < n), cari intervalı $j$ göstəricisini artıraraq genişləndiririk.

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

Əgər $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i, $i$ indeksi üçün cavabı çap edirik və $i$ -ni bir vahid artırırıq.

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

Alqoritmin realizasiyası — ikili axtarış, O(n log n)

Giriş məlumatlarını oxuyuruq.

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

Hər $i < n$ i < n indeksi üçün, ikili axtarış istifadə edərək, $A_{i}$ A_i-dən $2 \cdot A_{i}$ 2 \cdot A_i-yə qədər olan ədədlərin $[i; x - 1]$ [i; x - 1] intervalında yerləşdiyi və $A_{x} > 2 \cdot A_{i}$ A_x > 2 \cdot A_i olduğu ən böyük $x$ indeksi qiymətini tapırıq. $[i; x - 1]$ [i; x - 1] intervalındakı ədədlərin sayı $x - i$ x - i-yə bərabərdir.

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

Java realizasiyası

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 realizasiyası

Giriş məlumatlarını oxuyuruq.

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

$i = j = 0$ i = j = 0 göstəricilərini ilkinləşdiririk.

i = j = 0

Hər $i < n$ i < n qiyməti üçün cavab tapılana qədər göstəriciləri irəli aparırıq.

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

Əgər $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i (və $j$ massivin hüdudlarını aşmayıbsa, yəni $j < n$ j < n), cari intervalı $j$ göstəricisini artıraraq genişləndiririk.

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

Əgər $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i, $i$ indeksi üçün cavabı çap edirik və $i$ -ni bir vahid artırırıq.

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

Python realizasiyası — ikili axtarış, O(n log n)

from bisect import bisect_right

Giriş məlumatlarını oxuyuruq.

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

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