#微软笔试# #微软# #秋招# #笔试# #算法#
今日份（8-19）的微软笔试：
第一题：直接求解+二分优化。数据量N是10^5，数据大小M是10^9，从左往右直接求解，再使用二分优化一下，复杂度O(lg M)。当然，最大的问题在于无法证明这种做法是最优解，但是快就完事了！
第二题：贪心+堆优化。统计所有数出现的次数，对于任意两个数，当他们的数量都大于2、或者值都为1时，值更大的优先级更高；否则数量大于2的优先级更高。每次选择当前优先级最高的数，用于从两端向内组成回文，直至优先级最高的数无法再用于组成回文。
第三题：DFS。每次 DFS 返回一个 cost 和人数，当前点的 cost 、人数分别为由深层DFS返回的 cost 之和、人数之和，在当前非0的点返回前再对 cost 加上 ceil(当前人数/5)。