解题思路
根据类别约束条件,类别较小的任务必须分配较小的处理编号,因此三个类别的任务将按类别顺序依次占据连续的编号区间:
- 类别 0 的所有任务分配到编号 1,2,…,cnt0;
- 类别 1 的所有任务分配到编号 cnt0+1,…,cnt0+cnt1;
- 类别 2 的所有任务分配到编号 cnt0+cnt1+1,…,N。
在同类别的任务之间,编号的分配没有顺序限制,因此问题转化为:对每个类别,将给定的一组初始优先级 p 与一段连续的编号 s 进行匹配,使得该组内 ∑∣pi−si∣ 最小。这是一个经典的贪心问题:将两个数组分别排序后,按照大小顺序一一对应,即可使对应元素的绝对差之和最小。