如何实现无递归的正确最大小费计算器？修正现有算法错误

参数说明 #

• a、b：分别代表每个订单给工人A、工人B的小费
• n：订单总数
• x：工人A可处理的订单数量上限
• y：工人B可处理的订单数量上限

当前使用代码 #

def maxTip(self, a, b, n, x, y):
    idx=[[],[],[]]
    for i in range(len(a)):
        if a[i]>b[i]:
            idx[0].append(i)
        elif b[i]>a[i]:
            idx[1].append(i)
        else:
            idx[2].append(i)
    def findSum(arr):
        sum1=0
        sum2=0
    
        for index in idx[0]:
            sum1+=a[index]
            
        for index in idx[1]:
            sum2+=b[index]
        return sum1+sum2
    
    i=0
    while len(idx[0])<x:
        idx[0].append(idx[2][i])
        i+=1
    while len(idx[1])<y and i<len(idx[2]):
        idx[1].append(idx[2][i])
        i+=1
    return(findSum(idx))

原算法思路 #

遍历所有订单，将a[i]>b[i]的订单索引存入第一个子数组，b[i]>a[i]的存入第二个子数组，小费相等的存入第三个子数组；先把第三个子数组的订单补充给工人A直到达到x个，剩余的再补充给工人B直到达到y个，最后计算总小费。该算法仅在部分测试用例中有效，多数场景结果错误。

测试用例示例 #

有效测试用例 #

n=5 
x=3 
y=3 
a=[1,2,3,4,5] 
b=[5,4,3,2,1]

正确总小费为21，工人A处理订单3、4、5（小费总和12），工人B处理订单1、2（小费总和9）。

待解决测试用例 #

n=7
x=3
y=4
a=[8, 7, 5, 9, 6, 6, 8]
b=[1, 7, 5, 1, 2, 3, 9]

需修正算法以正确计算该用例的结果，且要求无递归实现。

问题分析 #

原算法的核心错误在于：

1. 未考虑a[i]>b[i]的订单数量超过x的情况——此时不能全部分配给A，必须选择其中差值a[i]-b[i]最大的x个，否则会损失更大的小费；同理，b[i]>a[i]的订单数量超过y时，也要选差值b[i]-a[i]最大的y个。
2. 分配相等小费的订单时，没有结合A、B剩余额度的合理性，只是无脑先给A，可能导致后续无法充分利用额度。

修正后的算法思路 #

1. 为每个订单计算差值diff = a[i] - b[i]，并将所有订单按这个差值从大到小排序：
   • 差值越大，说明给A比给B划算越多，优先分配给A；
   • 差值越小（甚至为负），说明给B比给A划算越多，优先分配给B。
2. 遍历排序后的订单，依次分配：
   • 如果当前订单给A更划算，且A还有剩余额度（x>0），则分配给A，累加a[i]，x减1；
   • 如果当前订单给B更划算，且B还有剩余额度（y>0），则分配给B，累加b[i]，y减1；
   • 如果差值为0（小费相等），则优先分配给剩余额度多的一方，或者任意一方（不影响总小费）。
3. 遍历完成后，累加的总和就是最大小费。

修正后的代码 #

def maxTip(self, a, b, n, x, y):
    # 生成包含索引和差值的列表，按差值降序排序
    orders = []
    for i in range(n):
        diff = a[i] - b[i]
        orders.append((diff, i))
    
    # 按差值从大到小排序，差值大的订单优先给A
    orders.sort(reverse=True)
    
    total = 0
    remaining_x = x
    remaining_y = y
    
    for diff, idx in orders:
        if diff > 0:
            # 给A更划算，优先分配给A
            if remaining_x > 0:
                total += a[idx]
                remaining_x -= 1
            else:
                # A没额度了，分配给B
                total += b[idx]
                remaining_y -= 1
        elif diff < 0:
            # 给B更划算，优先分配给B
            if remaining_y > 0:
                total += b[idx]
                remaining_y -= 1
            else:
                # B没额度了，分配给A
                total += a[idx]
                remaining_x -= 1
        else:
            # 小费相等，分配给剩余额度多的一方
            if remaining_x >= remaining_y and remaining_x > 0:
                total += a[idx]
                remaining_x -= 1
            elif remaining_y > 0:
                total += b[idx]
                remaining_y -= 1
    
    return total

测试验证 #

针对待解决测试用例，修正后的算法计算得出总小费为47，分配逻辑如下：

1. 差值最大的3个订单优先给A（索引3、0、4），累加9+8+6=23；
2. 剩余订单优先给B（索引5、6、1、2），累加3+9+7+5=24；
3. 总小费23+24=47，为正确结果。

内容的提问来源于stack exchange，提问作者VADeR