Üçlükləri Hesablamaq#9022

Üçlükləri Hesablamaq (Həll təhlili)

Üç massivin hamısını çeşidləyək. Hər bir $b_{j}$ b_j elementi üçün ikili axtarış vasitəsilə təyin edək:

$a$ massivində olan və $b_{j}$ b_j-dən kiçik olan $x$ elementlərinin sayını,
$c$ massivində olan və $b_{j}$ b_j-dən böyük olan $y$ elementlərinin sayını.

Beləliklə, sabit $b_{j}$ b_j dəyəri üçün $a_{i} < b_{j} < c_{k}$ a_i < b_j < c_k bərabərsizliyin təmin edən $(a_{i}, b_{j}, c_{k})$ (a_i, b_j, c_k) növündə dəqiq $x * y$ x * y üçlü mövcuddur.

Nümunə

Çeşidli massivləri nəzərdən keçirək və $b_{5} = 10$ b_5 = 10 üçün uyğun üçlüklərin sayını hesab edək.

Var: $a_{i} < b_{5}$ a_i < b_5 üçün $i \leq 5$ i \le 5, və $c_{k} > b_{5}$ c_k > b_5 üçün $k \geq 7$ k \ge 7.

Beləliklə, $a_{i} < b_{5} < c_{k}$ a_i < b_5 < c_k bərabərsizliyi $1 \leq i \leq 5$ 1 \le i \le 5 və $7 \leq k \leq 8$ 7 \le k \le 8 üçün yerinə yetirilir.

$(a_{i}, b_{5}, c_{k})$ (a_i, b_5, c_k) üçlüklərin sayı $5 * 2 = 10$ 5 * 2 = 10 bərabərdir.

Alqoritmin reallaşdırılması

İşçi massivləri elan edək.

#define MAX 100000
int a[MAX], b[MAX], c[MAX];

İnput massivləri oxuyuruq.

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

Massivləri çeşidləyirik.

sort(a, a + n);
sort(b, b + n);
sort(c, c + n);

Axtarılan üçlüklərin sayını $r es$ dəyişənində hesablayacağıq. $b_{j}$ b_j dəyərlərini nəzərdən keçiririk.

res = 0;
for (j = 0; j < n; j++)
{

$a$ massivində $b_{j}$ b_j-dən kiçik elementlərin sayı $x$ -ə bərabərdir.

  x = lower_bound(a, a + n, b[j]) - a;

$c$ massivində $b_{j}$ b_j-dən böyük elementlərin sayı $y$ -ə bərabərdir.

  y = n - (upper_bound(c, c + n, b[j]) - c);

Beləliklə, $b_{j}$ b_j dəyəri üçün dəqiq $x * y$ x * y axtarılan üçlü mövcuddur.

  res += x * y;
}

Cavabı çıxardırıq.

printf("%lld\n", res);

Java reallaşdırılması

import java.util.*;

public class Main 
{
  static int lower_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x <= m[mid])
         end = mid;
      else
        start = mid + 1;
    }
    return start;
  }

  static int upper_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x >= m[mid])
        start = mid + 1;
      else
        end = mid;
    }
    return start;
  }

  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);    
    int i, n = con.nextInt();
    int a[] = new int[n];
    for(i = 0; i < n; i++) a[i] = con.nextInt();

    int b[] = new int[n];
    for(i = 0; i < n; i++) b[i] = con.nextInt();

    int c[] = new int[n];
    for(i = 0; i < n; i++) c[i] = con.nextInt();

    Arrays.sort(a); Arrays.sort(b); Arrays.sort(c);
    
    long res = 0;
    for (i = 0; i < n; i++)
    {
      int x = lower_bound(a, 0, n, b[i]);
      int y = n - (upper_bound(c, 0, n, b[i]));
      res += 1L * x * y;
    }
    
    System.out.println(res);
    con.close();
  }
}

Java