Блог пользователя HCCoder

Нужна помошь в решние задачи
Автор HCCoder, история, 10 месяцев назад, По-русски

Вам дан массив a длины N и целое число k. Ваша задача — найти количество пар индексов (i, j), удовлетворяющих следующим условиям:

i < j

k * a[j] * a[i] > max(a[i], a[i+1], ..., a[j])

Входные данные:

N — длина массива (1 ≤ N ≤ 2 * 10^5);

k — целое число (1 ≤ k ≤ 10^4);

a[i] <= 1e9

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I can think of an idea derived from 2 famous algo

1) quick sort 2) divide and conquer

You find the max element that will act as the pivot than Partition into left and right Let x = value at pivot

From the left and right side find the smallest side

Let's assume left is smallest

So iterate through each element of left and than using fenwick find count of Value greater than ceil( x/ k * left[i])

Now do and divide

Now that we have 2 partition do and divide and conquer and solve for left and right

→ Ответить