ZOJ 3941

淩亂°似流年 2022-01-28 01:17 295阅读 0赞

题意：有n（10）段时间，会举行party，每个party有开始时间，结束时间，不同party举行时间可能重复。（时间范围为1~1e9） 我们一共最多可以参加m（1e9）party。同时有一个参数K（1e9），一旦我们在第i天参加了party，我们会连续K天（即[i,i+K-1]天范围内）都happy。问你我们如何安排参加party的时间，可以使得我们拥有尽可能多天数是happy的 分析：首先，我们显然要先把party排序并合并成不相交的日期段[b[i].first,b[i].second]，然后贪心。从最左边开始，依次选择长度k的区间，不相交，这样是最大的。但是这样贪心完之后发现m还有剩余，发现每个区间的最后一点也可以选，同样可以有增益效果，但是回头再去选，会打乱一开始的贪心，所以在贪心的时候就枚举每个区间，最后一个点要不要选，最后也就2的10次方种可能，爆搜一下就好了，注意细节问题。

代码参考：https://blog.csdn.net/dacc123/article/details/51279068

发表评论

表情：
评论列表 （有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读

    相关 zoj1002

    [题目传送门][Link 1] 题目大意： 在一个最大为4\4的方格内建blockhouse（ 碉堡） 但是有条件 1. 两个及以上blockhouse不能

    小灰灰小灰灰/ 0 赞/ 5 阅读

    相关 Zoj 2947——Abbreviation

    呵呵哒，一开始觉的很难，是因为题长，以后不能被长题再坑了！后来耐下性子读，才发现就是让比对缩写是否相同，我用字符数组写的，当时还开了二维数组，现在想来，实在是笨，不好意思再贴！

    电玩女神电玩女神/ 0 赞/ 249 阅读

    相关 ZOJ 3941

    题意：有n（10）段时间，会举行party，每个party有开始时间，结束时间，不同party举行时间可能重复。（时间范围为1~1e9） 我们一共最多可以参加m（1e9）

    淩亂°似流年淩亂°似流年/ 0 赞/ 296 阅读