首页 > 代码库 > 工作安排加强版(神奇的并查集)

工作安排加强版(神奇的并查集)

题目描述:

为了维持农场的运转,约翰必须打工赚钱。他接到了 N 份工作,每份工作恰好占用他一天的时间。约翰从第一天开始工作,他可以任意安排这些工作的顺序,第 i 份工作有 Pi 的报酬,但必须在第 Di 天结束之前完成。在截止日期后完成的工作没有报酬。请帮助约翰规划每天的工作,使得他赚到的钱最多。

1 ≤ N ≤ 105  , 1 ≤ Di ,Pi ≤ 109     这题就恶心在数据范围额。

 

解题过程:

1.这题寒假做贪心专题的时候做到过,贪心策略大致还记得,就是先按照报酬P从大到小排序,然后依次安排工作,(从Di开始往前找到第一个没有安排时间的节点)。但是看数据范围,呵呵呵呵。能过2个点。

2.一个优化:用一个father数组保存每个时间节点之前的第一个空位的位置。。  每次沿着father数组找到第一个空位。 然后高兴地提交了一下,还是2个点。。

3.专题名字是“并查集”,就尽量往并查集的方向想了。发现2中“每次沿着father数组找到第一个空位”的过程其实就是并查集的get_father。。那么就可以用并查集来写。当一个位置t已经被占用了,那么就merge(t-1,t)。 (注意要按顺序,必须是t所在集合连到t-1所在集合下面)。 然后又激动的提交了一下,还是2个点。。

4. 再次看了眼数据范围, 1 ≤ Di ,Pi ≤ 109        妈蛋还以为 Di的范围和N是一样的。。  那么father数组根本没法开到那么大。。。

5. 感觉思路应该是对的,所以尽量加些优化。。然后就想到可以根据Di离散化,按先Di排一下序,把Di,然后用 一个d[i]表示Di-Di-1  。 (去掉重复的点),做出每个Di对应的编号。 修改一下前面的算法,每次get_father找到第一个空位k,然后d[k]--,如果d[k]==0 ,就merge(k-1,k);   实践证明此方法可行。。 神奇的并查集。

 

工作安排加强版(神奇的并查集)