Yaxşı cütlər#9642

Yaxşı cütlər (Həll təhlili)

$a_{i} + a_{j} > b_{i} + b_{j}$ a_i + a_j > b_i + b_j şərtini aşağıdakı kimi yenidən yazaq:

a_{i} - b_{i} > - (a_{j} - b_{j})

a_i - b_i > – ( a_j - b_j)

$c$ fərqlərdən ibarət bir massiv quraq, burada $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i. Onu artan sıra ilə sıralayaq. $a_{i} - b_{i} > - (a_{j} - b_{j})$ a_i - b_i > - ( a_j - b_j) qeyri-bərabərliyi $c_{i} > - c_{j}$ c_i > - c_j ya eyni olan $c_{j} > - c_{i}$ c_j > - c_i bərabərliyinə ekvivalentdir. Bu qeyri-bərabərliyi həmçinin aşağıdakı formada yaza bilərik:

c_{i} + c_{j} > 0

c_i + c_j > 0

İndi hər bir indeks üçün $i (0 \leq i \leq n - 1)$ i~(0 \le i \le n - 1) minimal $j$ indeksini tapmalıyıq ki, $c_{j} > - c_{i}$ c_j > - c_i olsun. Şərtə uyğun olan bütün $j \leq k \leq n - 1$ j \le k \le n - 1 indeksləri üçün $(i, k)$ cütləri yaxşı olacaq. Lakin, cütləri iki dəfə hesaba almamaq üçün yalnız $k > i$ k > i olanları seçməliyik.

Nümunə

Göstərilən nümunəni nəzərdən keçirək. $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i massivini artan sıra ilə sıralayaq.

$t_{i} = 0$ t_i = 0 edək. Minimal $j$ indeksini axtarırıq ki, $c_{j} > - c_{0} = 3$ c_j > - c_0 = 3 olsun. Bu indeks $j = 4$ j = 4 olacaq. Beləliklə, $(0, 4)$ və $(0, 5)$ indeks cütləri yaxşı olacaq.

$i = 1$ i = 1 edək. Minimal $j$ indeksini axtarırıq ki, $c_{j} > - c_{1} = 1$ c_j > - c_1 = 1 olsun. Bu indeks $j = 3$ j = 3 olacaq. Beləliklə, $(1, 3), (1, 4)$ (1, 3), (1, 4) və $(1, 5)$ indeks cütləri yaxşı olacaq.

$i = 2$ i = 2 edək. $j = 3$ j = 3 olan minimal $j$ indeksini axtarırıq ki, $c_{j} > - c_{2} = 0$ c_j > - c_2 = 0. Beləliklə, $(2, 3), (2, 4)$ (2, 3), (2, 4) və $(2, 5)$ indeks cütləri yaxşı olacaq.

$i = 3$ i = 3 edək. $c_{j} > - c_{3} = - 3$ c_j > - c_3 = -3 olan minimal $j$ indeksini axtarırıq. Bu indeks $j = 1$ j = 1 olacaq. $(i, k)$ cütü yaxşı olacaq, əgər iki şərt təmini olunsa: $k \geq j$ k \ge j və $k > i$ k > i. Bu vəziyyətdə, $(3, 4)$ və $(3, 5)$ indeks cütləri yaxşı olacaq. (3, 1) və (3, 2) cütləri də yaxşıdır, lakin onlar artıq $i = 1 ((1, 3)$ i = 1~((1, 3) cütü) və $i = 2 ((2, 3)$ i = 2~((2, 3) cütü) hallarında nəzərə alınmışdılar.

$i = 4$ i = 4 edək. Yalnız yaxşı cüt $(4, 5)$ olacaq.

Ümumilikdə $11$ yaxşı indeks cütü var.

Alqoritmin realizasiyası

Giriş məlumatları oxumaq.

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

$c$ fərqlərdən ibarət bir massiv quraq, burada $c_{i} = a_{i} - b_{i}$ c_i = a_i - b_i.

c.resize(n);
for (i = 0; i < n; i++)
  c[i] = a[i] - b[i];

$c$ massivini artan sıra ilə düzün.

sort(c.begin(), c.end());

Yaxşı indeks cütlərinin sayını $r es$ dəyişənində toplayacağıq.

res = 0;

İndeksləri $i$ üzrə dolaşırıq.

for (i = 0; i < n; i++)
{

Hər bir indeks üçün $i$ , minimal $j$ indeksini tapaq ki, $c_{p os} > - c_{i}$ c_{pos} > - c_i olsun. Buradaxıçin $p os \geq i + 1$ pos \ge i + 1 şərti də yerinə yetirilməlidir.

  pos = lower_bound(c.begin() + i + 1, c.end(),-c[i] + 1) - c.begin();

Yaxşı olan bütün $(i, k)$ indeks cütləri, $p os \leq k \leq n - 1$ pos \le k \le n - 1 üçün olacaq. $k$ üçün olan belə dəyərlərin sayı $(n - 1) - p os + 1 = n - p os$ (n - 1) - pos + 1 = n - pos.

  res += n - pos;
}

Cavabı çap edək.

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