mengbierr

一个蒟蒻的博客

3月19

Codeforces377D. Developing Game

题目大意

有n个工人,第i个工人的能力是vi,他只与能力在li到ri之间的人在一起工作,问最多能选出多少人一起工作并输出方案。

题解

枚举能力值,对于第i个工人,枚举到vi时他会对答案有贡献,枚举到ri时他对答案没有贡献,那么将一个工人看成两个操作(li,vi,vi,1)和(li,vi,ri,-1),(a,b,c,d)代表操作区间为[a,b]加d,按c排序,然后在线段树上查询最大值即可。

(比较难以描述,还是看代码吧…)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注