《偶像的条件》题目分析
首先我们可以把ABC三个班的同学分别按身高从小到大排序。
然后枚举A班选出的同学,不妨设是Ai。
那么显然B班选出的同学一定是以下2人(也可能是同一人)之一:
1) 身高大于等于Ai的最矮的人
2) 身高小于等于Ai的最高的人
要求出这两个人的序号,我们可以在B班身高数组中二分,O(logM)得到。
也可以在Ai从A1枚举到AN的过程中,用类似滑动窗口的方法均摊O(1)得到。
同理,Ai确定的情况下,C班选出的同学也一定是以下2人(也可能是同一人)之一:
1) 身高大于等于Ai的最矮的人
2) 身高小于等于Ai的最高的人
这样B班和C班的组合一共有不超过4种情况,从其中选择最优的即可。
总时间复杂度O(NlogN+MlogM+LlogL)。