hiho一下第267周《偶像的条件》题目分析

0
0

《偶像的条件》题目分析

首先我们可以把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)。

1 answer(s)

2

我用的是贪心算法思路应该也是对的吧 大概的思路是: 1.先排序三个班级同学的身高; 2.从三个班级选出来身高最小的三位的分别是 a,b,c。 3.result = abs(a-b) + abs(b-c) + abs(a-c) 4.将a,b,c三位中身高最小的同学去掉,并从所在班级选下一位身高最小者 5.若a,b,c存在,跳转到步骤3,否则返回result

write answer 切换为英文 切换为中文


转发分享