每次操作都会丢掉当前选出的 m 个果筐中最轻的一个。为了让剩下的果筐尽量少,应当尽可能多地执行操作,并且优先丢掉较轻的果筐。
把重量排序后,第 i 小的果筐能被丢掉,当且仅当它与后边第 m−1 个(即 ai+m−1)之差不超过 k。对每个可能的左端点 i=1,…,n−m+1 检查一次即可。每成功一次就少留一个果筐。
时间复杂度 O(nlogn),空间复杂度 O(n)。
果园分拣线把 n 个果筐的重量记成一个可重集合。质检规程规定:每轮可以从集合中选出 m 个果筐,前提是这 m 个重量中最大值与最小值之差不超过容差 k,然后丢掉其中最轻的一个,其余放回集合。若无法再选出满足条件的 m 个果筐,分拣必须停止。分拣员可以任意安排操作顺序,目标是让最后剩下的果筐个数尽可能少。
约束:2≤m≤1000000,0≤k≤1000000000。
第一行三个整数 n、m 和 k,分别表示果筐个数、每轮选取个数与重量差上限。 第二行 n 个整数,表示各果筐重量。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.