首先考虑列出每辆车的总行驶路程:s=2*a[i]*p+2*b[i]*(x-p)
根据直觉,a[i]>b[i]的车应当优先分配靠左的p[x],a[i]<b[i]的车应该优先分配靠右的p[x],所以需要排序解决
那怎么排序呢?
在所有a[i]>b[i]的车中,贪心地想,a[i]越多的应该越靠左,但同时也要考虑b[i]的影响,所以应该是a[i]-b[i]越大的越靠左安排;(a[i]<b[i]同理)
证明:排序不等式 适用于代价两两不相关的交换/排序问题
假设对于两辆车i,j,i在p1,j在p2,如果把i移到j更优,就要求原来的总代价大于交换后的总代价,即:
然后贪心模拟即可,注意a[i]=b[i]的情况可以与a[i]>b[i]的情况一同处理变成a[i]>=b[i]