美团笔试（算法）程序题第二题，排序。
第一步：求总共的小盒子数量。
第二步：将盒子容量快速排序，并相应的更新已装盒子的顺序（快速排序应该用其他方法方法替换，实际上不用全部排序）
第三步：并贪心计算出需要的盒子数量k，得到选择的盒子中的最小的盒子容量xmin
第四步：将盒子容量等于xmin的盒子按照已装小盒子的数量逆序排列。需要的秒数t为第k+1到第n个盒子中装的小盒子的数量
第五步：输出k，t
遗憾的是没能按时提交，还差5分钟就可以检查出错误了。题目很简单，这个方法也肯定是比较粗糙的方法。没能按时完成，归根结底还是程序写少了。
import sys
import random
def quickSort(nums, value, l, r ):
"""快速排序一组一维数组"""
if l >= r:
return nums,value
p = partition(nums, value, l, r)
quickSort(nums, value, l, p-1)
quickSort(nums, value, p+1, r)
return nums, value
def partition(nums, value, l, r):
"""
遍历，交换,两个指针
对nums[l,...,r]进行partition操作
返回p，使得arr[l,...,p-1] <= arr[p]; arr[p+1,...,r] > arr[p]
"""
k = random.randint(l+1,r)
nums[l], nums[k] = nums[k], nums[l]
value[l], value[k] = value[k], value[l]
v = nums[l]
i = l+1 # arr[l+1,...,i) < v
j = r # arr(j,...,r] > v
while True:
while (i <= r) and (nums[i] > v):
i +=1
while (j >= l+1) and (nums[j] < v):
j -=1
if i > j:
break
nums[i],nums[j] = nums[j], nums[i]
value[i], value[j] = value[j], value[i]
i +=1
j -=1
nums[l],nums[j] = nums[j], nums[l]
value[l], value[j] = value[j], value[l]
return j
if __name__ == "__main__":
# 读取第一行的n
# n = int(sys.stdin.readline().strip())
# line = sys.stdin.readline().strip()
# Y = list(map(int, line.split()))
# line = sys.stdin.readline().strip()
# X = list(map(int, line.split()))
# 测试例子
n = 10
Y = [6,3,3,3,5,3,2,1,1,3]
X = [8,6,6,6,6,4,5,4,6,6]
sel_box = 0
for i in range(n):
sel_box = sel_box+Y[i]
# X快排
l ,r = 0, n-1
X, Y = quickSort(X, Y, l, r)
# 寻找k和h
total_box = 0
for i in range(n):
total_box = total_box+X[i]
if total_box >= sel_box:
k = i
l = i
while (l >= 0) & (X[l] == X[i]):
l = l - 1
l = l+1
r = i
while (r < n) & (X[r] == X[i]):
r = r + 1
r = r-1
break
Y, X = quickSort(Y, X, l, r)
t = 0
for i in range(k+1,n):
t = t+Y[i]
print(k+1,t) 
OPPO公司福利 1172人发布