Распределение продуктов HackerRank

Question

Я пытался решить эту проблему и кое-что понял, что делать. Но после всех моих попыток я могу пройти только контрольные тесты и еще один кейс на панели отправки. Все сбои после этого

ПРОБЛЕМА:

Компания запросила упорядочить свою стратегию распределения продуктов, и, учитывая n продуктов, каждый из которых имеет ассоциированное значение, вы Требуется организовать эти продукты в сегменты для обработки. Есть бесконечные сегменты, проиндексированные как 1, 2, 3 и т. Д.

Однако есть два ограничения:

• Вы можете назначить продукт сегменту с индексом i, если и только если i = 1 или сегмент с индексом i-1 имеет не менее m продуктов.
• Любой сегмент не должен содержать ни продуктов, либо по меньшей мере m продуктов.

Оценка для сегмент определяется как индекс сегмента, умноженный на сумму значений продуктов, которые он содержит. Оценка расположения продуктов - это сумма оценок сегментов. Ваша задача - вычислить максимальный балл для организации.

Рассмотрим, например, n = 11 товаров и m = 3. Один из оптимальных способов присвоения -

1. Назначить первые три продукта для сегмента 1.
2. Назначьте следующие три продукта для сегмента 2.
3. Назначьте следующие пять продуктов для сегмента 3.

Обратите внимание, что мы можем не назначайте 2 продукта сегменту 4, поскольку второе ограничение будет нарушено. Счет вышеупомянутой договоренности - -

1 * (1 + 2 + 3) + 2 * (4 + 5 + 6) + 3 * (7 + 8 + 9 + 10 + 11) = 6 + 30 + 135 = 171.

Поскольку показатель аранжировки может быть очень большим, выведите его по модулю 10 ^ 9 + 7.

Формат ввода

В первой строке есть два целых числа через пробел n и m.

Во второй строке есть n целых чисел через разделенный пробел a0, a1, ...., an-1, обозначающие значения, связанные с ними. с продуктами.

Ограничения

• 1 <= n <= 10 ^ 6 </li>
• 1 <= m <= n </li>
• 1 <= ai <= 10 ^ 9 </li>

Формат вывода

В единственной строке выведите одно целое число, обозначающее максимальную оценку расположение по модулю 10 ^ 9 + 7.

Пример ввода 0

5 2
1 5 4 2 3

Пример вывода 0

27

Объяснение 0

Массив a = [1,5,4,2,3] и m = 2. Оптимально поместить первый и четвертый продукты в файл. Первый сегмент и остальные продукты для второго сегмента. Делая это, мы получаем оценку аранжировки (1 + 2) * 1 + (3 + 4 + 5) * 2 = 27, которая является наибольшим баллом, который можно получить. Наконец, ответ по модулю 10 ^ 9 + 7, который равен 27.

Пример ввода 1

4 4
4 1 9 7

Пример вывода 1

21

Пояснение 1

Все четыре продукта должны быть размещены в первом сегменте. Оценка в этом случае будет 1 * (4 + 1 + 9 + 7) = 21.

МОЕ РЕШЕНИЕ

Теперь то, что я выяснил, объясняется в Мой алгоритм:

1. Чтобы проверить, равна ли длина массива == m, если да, вернуть сумму всех элементов
2. Если нет, возьмите start = 0 и end = m, как указатель, который будет заботиться о сумме элементов до этой части start -> end
3. Сортировать массив для достижения наилучших результатов
4. Take batch = 1, который будет увеличен в в то время как l oop и умножается на сумму массива ограниченных продуктов
5. Для остальных элементов в массиве выполните ту же операцию batch * (sum of elements from start till end)
6. Добавьте его в maxSum и верните maxSum

Код

def maxScore(segment, products):
    # Write your code here
    # If the segment == products, then it should return all the sum
    # We will evaluate as per the products listing requirement and find the sum

    '''
        Algo for else condition
        1. We will maintain a start and end pointer to keep a check till counter equals products
        2. We will keep adding the maxSum of the value [i * sum(batch of the element)]
        3. Come out of the loop and perform a final operation as above with the remaining elements
        4. Add it to sum
        5. Return maxSum
    '''
    batch = 1
    maxSum = 0
    start = 0 
    end = products
    segment.sort()
    if len(segment) == products:
        maxSum += (batch * sumElem(segment[start:len(segment)]))
    else: 
        while batch != products:
            maxSum += (batch * sumElem(segment[start:end]))
            batch += 1
            start += products
            end += products
        maxSum += (batch * sumElem(segment[start:len(segment)]))
    return maxSum

# function to find the sum of the elements
def sumElem(arr):
    total = 0
    for item in arr: total += item
    return total

Другое решение:

def maxScore(segment, products):
    # Write your code here
    # If the segment == products, then it should return all the sum
    # We will evaluate as per the products listing requirement and find the sum

    '''
        Algo for else condition
        1. We will maintain a start and end pointer to keep a check till counter equals products
        2. We will keep adding the maxSum of the value [i * sum(batch of the element)]
        3. Come out of the loop and perform a final operation as above with the remaining elements
        4. Add it to sum
        5. Return maxSum
    '''
    batch = 1
    maxSum = 0
    start = 0 
    end = products
    segment.sort()
    while batch != products:
      maxSum += (batch * sumElem(segment[start:end]))
      batch += 1
      start += products
      end += products
    maxSum += (batch * sumElem(segment[start:len(segment)]))
    return maxSum

# function to find the sum of the elements
def sumElem(arr):
    total = 0
    for item in arr: total += item
    return total

После всех испытаний , the code works fine for all the visible test cases, but doesn't pass any of the hidden test cases on HackerRank. Мне нужна помощь в этом, я думаю, что произошло какое-то недоразумение в понимании вопроса, потому что решение кажется мне подходящим