给定n个函数yi（x）=a0+a1x+a2x2+a3x3和q查询

Question

给定n个函数yi（x）=a0+a1x+a2x2+a3x3和q查询。对于每次查询，我们都会得到一个整数t，我们需要找出使yi（t）最小化的yi。在

supoose我们有一个列表列表，其中包含n个函数[[10，5，4，8]，[2，0，5，0]，[1，8，0，2]，[8，7，8，7]，[7，0，8，1]]的值，并且对于不同的t值，我们必须找到t值最小的函数。例如t=1，函数[2,0,5，0]是最小值。我尝试了一种暴力方法，但对于n值较大和t值不同的大值，脚本执行速度太慢。在

lis= [[10, 5, 4, 8],[2, 0 ,5, 0],[1, 8, 0, 2],[8, 7, 8, 7],[7, 0, 8, 1]]
t=[1,3,5,7,9]
size=len(lis)
for j in t:
    matrix=[]
    for i in range(size):
        matrix.append(lis[i][0] + j*((lis[i][1]) + j*((lis[i][2]) + (lis[i][3]*j))))

    print(min(matrix))  

输出：7 47 127 247 407

Answer 1

我没有一个完整的答案，但也许有些想法可以加快速度。在

目前还不完全清楚大量的三次多项式是从哪里来的，但是如果它们不是完全随机的，就有可能减少集合。在

例如，如果我有一个函数f（x）=ax^3+bx^2+cx+d，而另一个函数g（x）=ax^3+bx^2+cx+（d+e），则g（x）可以从集合中消除，因为g（x）=f（x）+e，因此总是大于f（x）。在

用二次项也可以做同样的事情。如果发现g（x）=f（x）+ex^2，当e>；0时，g（x）可以消除，因为二次项大于或等于零。在

由于多项式数组的排序复杂度为O（nlogn），因此排序不会造成影响（我们处理的复杂度为O（nm），其中n=多项式数，m=输入数）。 扫描阵列的复杂度为O（n），而且也不会造成伤害。在

立方体前面有大的正系数的多项式将是大负输入的有希望的候选多项式，反之亦然。 只要多项式相似，这个想法就可以用来减少搜索。在