滴滴 9.19 笔试：二分答案与花朵选取贪心

《面试题目》

1. 选择题 20 题，大部分是八股
2. 编程题 T1：有 n 台机器温度过高，每次选择一台机器进行降温，被选择的机器降温 a 度，其他机器降温 b 度，求最少需要几次操作使得所有机器温度都小于 0
3. 编程题 T2：有 n 只花，每只花都有编号 t 和魅力值 d，求选 k 只花使得它们的总价值最大。总价值分两部分：所有花的魅力值相加得到 s，再加上 k 只花中不同编号数量 x 的平方，也就是最大化 s + x²，期望复杂度 O(n log n)

《参考解析》

1. T1 用二分答案。二分操作次数 m，判断「m 次操作能不能让所有温度都小于 0」。设第 i 台机器被选中 c_i 次（Σc_i = m），它的总降温是 c_i·a + (m − c_i)·b = m·b + c_i·(a − b)。当 a > b 时，每台机器需要的最小选中次数是 c_i = max(0, floor((T_i − m·b) / (a − b)) + 1)（含义是「靠公共降温 b 还不够的部分，每被选中一次额外多降 a − b」），把所有 c_i 加起来，只要 Σc_i ≤ m 就说明 m 次够用——多出来的次数随便给哪台都只会让它降得更多，不会破坏可行性。可行性关于 m 单调（m 越大越容易满足），所以可以直接对 m 二分，复杂度 O(n log(maxT))。两个边界必须想到：a == b 时退化成一刀切，答案是 max(ceil((T_i + 1) / a))；a < b 时「被选中的机器反而降得少」，上面那个公式的前提没了，正确策略变成每次都必须选当前温度最高的机器，直接贪心模拟即可。

2. T2 要枚举不同编号的个数 x。总价值是 s + x²，其中 x 只有 1..min(k, 不同编号数) 种可能，可以直接枚举。固定 x 之后问题变成「选 k 只花、恰好用 x 个编号、让魅力值之和 s 最大」：先把每个编号内部按 d 降序排好，取「每个编号的最大 d」中的前 x 大（这 x 个编号各出一只），再从剩余所有花（包含这 x 个编号里的次大值）中取 k − x 个最大的，两者相加就是该 x 下的最大 s；对每个 x 算 s + x² 取最大值。用两个堆维护「已选中集合」和「候选集合」，枚举 x 时增量更新即可做到 O(n log n)。为什么不能只贪心取 d 最大的 k 只：x² 的边际收益是递增的（第 x 个新编号带来的增量是 x² − (x−1)² = 2x − 1），所以「多引入一个编号、牺牲一点 d」在 x 较大时可能是划算的，必须枚举取舍——这正是作者那份 O(n log n) 贪心只过了 0.82 的原因。如果 n 不大（几千以内），直接对 x 做 DP 或暴力反而更稳；还要注意 d 可能有负数，以及 k 等于 n 时 x 被总编号数卡死。

3. 笔试策略。选择题 20 题以八股为主（操作系统、网络、数据库、语言基础），是拉分最快也最稳的部分，值得优先保证正确率；编程题先写暴力保证拿到基础分，再优化到目标复杂度，读题时圈出「严格小于」还是「小于等于」、「温度小于 0」还是「不大于 0」这类边界；交卷前用极端输入（n = 1、所有值相同、k = n、答案无解）快速过一遍自己的代码。