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

please anyone help me in solving this
Автор helloIamCristiano, история, 2 года назад, По-английски

We have 2 arrays $$$A$$$ and $$$B$$$ of length $$$n$$$ each. We are required to pick $$$k$$$ elements from both the arrays say $$$A_{i_{1}}, A_{i_{2}}, ... A_{i_{k}}$$$ and $$$B_{i_{1}}, B_{i_{2}}, ... B_{i_{k}}$$$ such that the sum $$$A_{i_{1}} + A_{i_{2}} + ... + A_{i_{k}} > \lfloor{\frac{S_{A}}{2}}\rfloor$$$ and $$$B_{i_{1}} + B_{i_{2}} + ... + B_{i_{k}} > \lfloor{\frac{S_{B}}{2}}\rfloor$$$. Here $$$S_{A}$$$ and $$$S_{B}$$$ denote the sum of the arrays A and B respectively.$$$\newline$$$ We also want to print the indices we have chosen, if such a choice is possible.$$$\newline$$$ Also, pay attention to the fact that we are picking elements from $$$B$$$ with the same indices $$${i_{1}, i_{2}, ... , i_{k}}$$$ that we have used for $$$A$$$.$$$\newline$$$ Constraints :- $$$A_{i}, B_{i} \le 10^{9}$$$ and, size of the arrays $$$\le 10^{5}$$$. Please can anyone help me in solving this??

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

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

use priority queue or just sort the array to pick the K largest element from the array

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

Can you send the link to this problem?

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

Not sure if this solution works, but here it is:

Let Sa = sum of all elements of A, divided by two.

Similarly, Sb = sum of all elements of B divided by two.

In beginning, choose the max K numbers from array A. If their sum is smaller than Sa, the answer obviously does not exist. Otherwise, run a While loop, in condition: while the sum of chosen elements of B is smaller than the desired sum (that is, Sb), find an initially chosen index i, such that it has the least value of Ai. ( Note that once we change this i, we cant change it anymore). Then set that index to the position of the highest value of B that we haven't chosen that position yet, update the answer and check again if the current sum of chosen elements is ≥ Sb. Keep doing this until the answer is not found. If at some point inside the While, sum of chosen elements of A becomes less than Sa, then the answer doesn't exist.

→ Ответить