HDOJ Monthly 2009.01 Problem "light"
http://acm.hdu.edu.cn/showproblem.php?pid=3275
这个题目比较简单。。。
我刚开始写的解题报告里面说：
Greedy and Segment Tree will be worked at this problem.
We need change all “0” to “1”, so let’s put our attention on the first lantern of the given string. There is only one way to change states of first lantern which is installing a switch to control the first k lanterns.
Algorithm:
- If the first lantern is off then install a switch to change the states of first k lanterns.
- Let the second lantern be the first one and repeat Step 1 until there are less than k lanterns.
- If all of the remaining lanterns are on then output the answer else output “-1”.
Native solution will get TLE as it’s running in O(n * k).
A new accelerated date structure should be used to storage all the states of lanterns. This date structure should support two operators.
- Find the states of one lantern.
- Change all states of an interval.
Segment Tree will be worked.
这里说的线段树其实就是区间覆盖那种，统计一个点的奇偶值就查看这个点被覆盖的总数就好了。
因为这里的区间的大小总是K，所以其实用不着线段树，线性扫描就好了。。。
