USACO问题求USACO 1.2 那个 Milking Cows 的题解,急~~~~~

来源：学生作业帮编辑：作业帮分类：综合作业时间：2024/05/22 06:14:35

USACO问题
求USACO 1.2 那个 Milking Cows 的题解,急~~~~~

有两种思想
[编辑] 离散化
（其实就是进行了优化的搜索而已）
按照开始时间升序排序,然后从左到右扫一遍,复杂度是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}
看不懂?去看看PASCAL或C++的范例程序就明白了.
[编辑] 线段树
本题的规模是1e6,简单的模拟是O(nm)(n是奶牛个数,m是最大范围)的,会超时.(但是本题数据远没有描述的那么恐怖,直接模拟也是很快的}
用线段树统计区间,复杂度降为O(nlogm+m),可以接受.
[编辑] 标记数组（哈希）
1e6的范围,开一个布尔数组完全可以,有人为TRUE,无人为FALSE,注意边界即可.最后线性扫描即可.
时间复杂度,应该是O(n),n为最后结束的时间.
[编辑] 叫什么好呢?并查集加速直接模拟
记录一个fa[i]表示i之后第一个没覆盖的点.下次遇到这里的时候就可以直接跳过了.复杂度大概算o（n）吧.
这道当然用标记数组更好
我usaco都快刷完了加油啊

英语翻译是USACO中全题哦 usaco friday the thirteenth usaco 里的Friday the Thirteenth请牛人帮忙 usaco 1.1.3.Friday(黑色星期五) 关于USACO我做的dualpal测试点全过后.祝贺变成了USER: Nick A [sw20111]TASK: dua A man is milking the cows.什么意思求大神帮助 2001 USACO 绿组奶牛表达式 (要求用PASCAL语言编写) USACO Greedy Gift GiversA group of NP (2 ≤ NP ≤ 10) uniquely 英语翻译1.we're milking cows.我们正在挤牛奶.2.we're catching the train. sings cows cameras parks选出音标不同的那个求61题解(英语)急! 不好意思啊~还有个问题,我之前问你的那个问题解出来的直线方程绕Y轴旋转一周所得的曲面方程怎么求?