本文主要是介绍（CSP2019模拟）DTOJ 4617. 逛公园，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
小凯做题做累了，他想去逛公园。
公园里有 m m m 个亲子项目，每个项目一天只能一个家庭参加。一共有 n n n 个家庭，第 i i i 个家庭希望在第 l i l_i li 到 r i r_i ri 天内参加恰好一次第 p i p_i pi 个项目。但是公园的工作人员很懒，他们希望上班的天数尽量少。某天要上班当且仅当至少有一个家庭参加了任意一个项目。
工作人员看到了小凯，想让他帮忙使得工作人员有更多咕咕咕的机会。但小凯又双叒叕不会了，所以他请你求出这个最少的上班时间。如果无论如何安排都不能达到要求，输出 GG。
subtask1(20pts) n , m , l i , r i ≤ 8 n,m, l_i,ri \le 8 n,m,li,ri≤8
subtask2(30pts) n , l i , r i ≤ 1 0 5 , m = 1 n,l_i,r_i \le 10^5,m = 1 n,li,ri≤105,m=1
subtask3(50pts) 无任何限制
对于100%的数据 n ≤ 1 0 5 , l , r , m ≤ 1 0 9 n \le 10^5, l,r,m \le 10^9 n≤105,l,r,m≤109
题解
贪心地想，每次取目前右端点的最小值，在这个位置上工作一天，再把每个项目右端点最小的区间放到这上面，在可行的条件下一定是最优的。
但可能有多个相同项目的区间有相同的右端点，此时有一些要取到前面一点的，这可以看作把一些区间的右端点往前移。考虑能否把一个项目所有区间的右端点变为互不相同的，对于每一个项目，先算出右端点要缩到哪些，然后按左端点从大到小分配，若有分配到的区间为空则不合法，否则按照前面的贪心做即可。
这篇关于（CSP2019模拟）DTOJ 4617. 逛公园的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
