滴滴笔试-滴滴8月30日机考笔试题与解析

《面试题目》

1. 请计算所有绑定方案里，总残差的最小值？

《参考解析》

1. 请计算所有绑定方案里，总残差的最小值。 设所有配对的和为 S，若一对和不小于 q，取模会使结果减少 q，因此目标等价于最大化满足 u+v≥q 的配对数。将 u、v 升序排序：用指针分别指向 u 的最小值和 v 的最大值；若两者之和≥q，就计数并同时移动两指针，否则最小的 u 连最大的 v 仍不足 q，该 u 不可能形成合格配对，只移动 u。设最大数量为 c，答案为 S-c×q，复杂度 O(k log k)，额外空间 O(1)（不计排序开销）。

原帖：https://www.nowcoder.com/discuss/923736339126722560