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

Is my Approach wrong?
Автор TTMMM, история, 5 лет назад, По-английски

Submission ID: 66585414 Problem : 1201/C C. Maximum Median

I am first calculating that for median to be ar[i], can we go there by swapping? Once done, all elements in second half of array are equal and i am still left with k, its easy to increase median by increasing all elements by 1 each. Please tell if this approach is fine or not, Getting WA at test case 6

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

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

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

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

Greedy approach:
First sort the given array it's obvious that element from [0,n/2[ have no influence in the final answer.
for each element in the second half of the array, you have to make the median equals to a[i+1] if it's possible so you should make all element from [n/2, i] equals a[i+1] (don't forget the case when you still have k and you can make changes)
For example/
9 6
1 2 2 2 5 5 6 6 7
The first step make the array equals to :
1 2 2 2 6 6 6 6 7
then
1 2 2 2 7 7 7 7 7
My submission : 66587248
I found bs approach explained in the editorial much easier.

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

    Thanks bro. This is exactly what I have done. Just that my solution is not getting accepted, but the logic is same. Found now where i had gone wrong.

    → Ответить