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

Sum of all absolute values in two arrays
Автор Vasiljko, история, 9 лет назад, По-английски

Given two arrays A and B of size N. Let's take A={4,2,8} AND B={2,7,3}. All possible absolute values are 1: |4-2|+|4-7|+|4-3|=6 ; 2: |2-2|+|2-7|+|2-3|=6 ; 3: |8-2|+|8-7|+|8-3|=12; Sum of all these is 6+6+12=24;

Constraints : 1<=N<=10^5 , |Ai|,|Bi|<=10^6, so Ai,Bi can be negative

Any help with solution with time complexity O(nlogn)?

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

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

Auto comment: topic has been updated by Vasiljko (previous revision, new revision, compare).

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

Please problem link ?

→ Ответить
»
9 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

We can first sort both arrays ----O(nlogn)

Now we can find in how pairs each element will be greater element(we add this many times ot the sum) and in how many it will be smaller one using binary search. We do this for all elements(we subtract this many times from sum) --O(nlogn)(we can even do two pointers --O(n))

Total = O(nlogn)

→ Ответить