【CCPC2020绵阳站】J - Joy of Handcraft

标签:lazy   code   pc2   时间   log   load   区间   想法   mamicode   

原题:

技术图片

 

 题意:

给你m个灯,每个等有一个周期ti,和一个亮度xi,第i个灯先亮ti秒,再灭ti秒,再亮ti秒,每次亮度都是xi

同一时间如果有多个灯亮,那么场地亮度是最大值

给你一个n,问你从第1秒直到第n秒的每一秒,场地的亮度是多少

 

朴素的想法:

对于每个灯,枚举它亮的区间,用线段树区间取max取做

实际的做法:

根据调和级数求和,上述做法的时间复杂度为O(mlognlogn)

然后就可以愉快地AC了

据说正解是线段树合并,mlogn,不过出题人很良心,两个log放过去了,大力点好评

(调和级数我没想到,若干个小时后买志斌才去看到这个题,然后就秒了)

 

没有代码

【CCPC2020绵阳站】J - Joy of Handcraft

标签:lazy   code   pc2   时间   log   load   区间   想法   mamicode   

原文地址:https://www.cnblogs.com/cdcq/p/13910196.html

版权声明:完美者 发表于 2020-11-01 22:21:56。
转载请注明:【CCPC2020绵阳站】J - Joy of Handcraft | 完美导航

暂无评论

暂无评论...