为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/milk2
- 这是USACO Chapter 1 .2中的OI题目Milking Cows的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 分析
有四种思想
[编辑] 离散化
（其实就是进行了优化的搜索而已）
按照开始时间升序排序，然后从左到右扫一遍，复杂度是O(nlogn+n)的（排序+扫一遍，用堆、合并、快排都可以）。
所谓从左到右扫一遍，就是记录一个当前区间，[tmp_begin , tmp_end]
如果下一组数据的begin比tmp_end的小（或相等），则是连接起来的，检查这组数据的end，取max{end , tmp_end}。
如果下一组数据的begin比tmp_end的大，则是相互断开的，整理本区间，ans1取max{tmp_end - tmp_begin , ans1}。ans2取max{begin - tmp_end , ans2}
我觉得其实是不用排序的
设bi,ei分别为第i个输入inc(map[bi]);dec(map[ei])
记录下min_x和max_y,从min_x到max~y-1扫描,分别统计最大的连续0的个数、连续非零数的个数
缺点是代码很长啊。。
[编辑] 线段树
本题的规模是1e6，简单的模拟是O(nm)(n是奶牛个数，m是最大范围)的，会超时。(但是本题数据远没有描述的那么恐怖,直接模拟也是很快的}
用线段树统计区间，复杂度降为O(nlogm+m)，可以接受。
[编辑] 怀疑是线段树的变形？
把每个输入看作是一个所谓的“线段”，只有开头和结尾。
既然每条线段有重叠现象，马上想出可以合并！按照开头和结尾从小到大排序，for一遍，如果发现前后两条线段开头与结尾重叠了，
（当然也要考虑被完全包括的情况），马上修改开头与结尾，并删除（可以标记），最后在剩下的线段中统计就可以了。
（好像非常易懂，也很容易实现）
[编辑] 标记数组（哈希）
1e6的范围，开一个布尔数组完全可以，有人为TRUE，无人为FALSE，注意边界即可。最后线性扫描即可。
时间复杂度，应该是O(n),n为最后结束的时间。
缺点就是……比较慢
和我的方法比较像，但我做了些优化
预处理：
建立一个数组a。
读入，若为起点将a[i]加1，若为终点将a[i]减1。
（这时顺便找出总的起点与终点）；
算法开始：
将数组扫一遍（注意从总的起点扫到总的终点），这时将x（初始为0）加上a[i]。
若遇到x由0变1，或由1变0，
将这个点计入数组ans[]。
然后再将ans扫描一遍，大家可能都想到了：
若i为奇数，ans[i+1]-ans[i] 应该是有人的时间间隔；
若i为偶数，反之。
这个算法是O(n)，实际效果不错，但我也不知道应该叫什么。
回楼上的话，这种方法可以称之为是差分。见noip2012提高组 借教室。具体指有一列数字a，
再找来一个数组s记录相邻数字之差，这样每个数字a[i]都是s[1]+s[2]+...+s[i-1]。对于一
段数字的加减法就可以通过将这一段开头的差加上相应的数字，再把这一段结尾的数字减去相
应的数值即可。很巧妙的方法。
[编辑] 叫什么好呢？并查集加速直接模拟
记录一个fa[i]表示i之后第一个没覆盖的点。 下次遇到这里的时候就可以直接跳过了。 复杂度大概算o（n）吧。
[编辑] 分段动规
消逝者--183.16.23.147 22:26 2011年11月3日 (CST)
时间复杂度（nlogn),全部0毫秒。
以开始时间从小到大快排每个农民
快排后：
f[i]表示第i个农民所在的最长连续线段
last_start表示这个线段的起点。
a[i].begin 第i个农民的起点时间，a[i].end 终点时间
可以得出方程：
f[i]={max{f[i-1],a[i].end} (a[i].begin<=f[i-1]) //加上第i个农民仍然连续
a[i].end (a[i].begin>f[i-1]) /*加上第i个农民变不连续
在这里开始以此农民的开始时间的新的一条连续线段，
更新last_start=a[i].begin作为新起点，因为有间隔，
所以更新longest_idle_time=max(longest_idle_time,a[i].begin-f[i-1]);*/
在每次循环处理后longest_continuous_time=max(longest_continuous_time,f[i]-last_start) 最后输出longest_continuous_time和longest_idle_time即可。
