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

can somebody help me solve this problem please? no idea how to solve it
Автор Astroflexx, история, 2 месяца назад, По-английски

Given an array of integers and an integer m, in one operation, choose atmost m numbers of the array and increment them.

What is the minimum no of operations to make all the elements in the array equal?

1 <= nums[i] <= 1e5

1 <= m <= 1e5

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

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

.

→ Ответить
»
2 месяца назад, # |
← Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

assuming the numbers are incremented by one i think you can just sort the array and the biggest value minus the smallest would be the answer

why are you people upvoting my wrong solution this solution is wrong i posted the right one in the replies grahhhhh

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

    nevermind i realized the issue with this approach i am so terrible at this. this doesnt work if the m integer is smaller

    then i think you just sort an array and then while the smallest integer is smaller than the biggest you increment the smallest integers in the array with a for loop if the array is not smaller then the loop breaks

    we add 1 to the counter and sort the array at the end of a while loop as well

    i have no idea how to phrase any of this better i myself am probably on the same level of coding

    heres the lump of python code that I THINK works:

    t = int(input())  # num of iterations


def calc():
    c = 0
    a = list(map(int, input().split()))
    m = int(input())
    a.sort()

    while a[0] < a[len(a)-1]:

        a.sort()
        for i in range(m):
            if a[i] < a[len(a)-1]:
                a[i] = a[i] + 1
            else:
                break
        a.sort() # added this after posting and realizing that sometimes the first num in the array can be the same size as the last but not the other ones
        c = c + 1  # the loop that repeats while the smallest int is smaller than the biggest; we check if the value is smaller than the biggest and if it is, we increment it; we also add 1 to the counter each "while" repetition

    print(c)


for i in range(t):
    calc()

# i think this kinda works
    → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

bro do paste the question link

→ Ответить
»
2 месяца назад, # |
← Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

I think this works.

def solve(nums, m):
    mx = max(nums)
    a = [mx - i for i in nums]
    return max(max(a), (sum(a) + m - 1) // m)
→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i think u just have to sum the difference between max and every other element in the array, and then divide the sum by m, ceil(sum), to ensure that if there were remainders, it can be rounded up.

→ Ответить