arrays - HackerRank 产品分布

Question

我一直在努力解决这个挑战，并且有点想知道该怎么做。但是经过我所有的尝试，我只能通过测试用例，并且在提交面板中还有一个案例。之后一切都失败了

问题:

一家公司要求简化其产品分配策略，给定 n 个产品，每个产品都有一个关联值，您需要将这些产品排列成多个段进行处理。有无限段索引为 1、2、3 等。

但是，有两个限制条件:

• 当且仅当 i = 1 或索引 i-1 的分割至少有 m 种产品时，您才可以将产品分配给索引为 i 的分割。
• 任何分割必须不包含任何产品或至少包含 m 个产品。

分割市场的分数定义为分割市场的指数乘以其包含的产品的值(value)总和。产品排列的分数是段分数的总和。您的任务是计算排列的最高分数。

例如，考虑 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
• 1 <= m <= n
• 1 <= ai <= 10^9

输出格式

在一行中，打印一个整数，表示以 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 * (4 + 1 + 9 + 7) = 21。

我的解决方案

现在我的算法解释了我的想法:

1. To check if the array length == m, if yes, return the sum of all elements
2. If not, take start = 0 and end = m, as a pointer which will take care of the sum of the elements till that part start -> end
3. Sort the array for best results
4. Take batch = 1, which will be incremented in a while loop, and multiplied with the sum of the limited products array
5. For remaining elements in the array, do same operation batch * (sum of elements from start till end)
6. Add it to the maxSum and return the 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

在所有测试之后，代码对于所有可见的测试用例都运行良好，但没有通过 HackerRank 上的任何隐藏测试用例。我需要一些帮助，我想在理解这个问题时发生了某种误解，因为解决方案对我来说似乎很好

Answer 1

我们首先对给定的数组进行排序。这是因为我们最终“分段”的数字越大，总和就会越大，而且它会乘以分段的索引，从而使输出最大化。

解决该问题的简单逻辑是找到具有m 产品的最大段数。在示例输入中，对于输入 n=5，m=2:我们最多可以用 2 个产品形成 1 个分割市场，因为如果我们用 2 个产品分割为 2 个分割市场，最后我们只剩下 1 个产品，我们无法对其进行分割(根据问题)。

为了实现这一点，我们将字符串的长度除以 m，如果不能完全整除，则从中减去 1。

def maxScore(a, m):

a.sort()
print(a)
x=len(a)

if x%m==0:
    y=int(x/m)
else:
    y=int(x/m)-1

summ=0
count=1
#print(y)
i=0
for _ in range(y): 
    summ=summ+(sum(a[i:i+m])*count)
    count=count+1
    i=i+m
    print(summ)

summ=summ+sum(a[i:])*count
print(summ)

return summ%1000000007