Tag Archives: Binary Search

[ACM] POJ 1727 解题报告, 二分+贪心

思路和yzhw牛一样

1. 每一个event它对应的可能的cause是这个event点下面的三角形区域(这个区域是无穷大的)
2. 问 “the latest time at which the earliest cause could have occurred” 就相当于用一条平行于x轴的直线 t=t0 把这些三角形区域拦腰切断(当然, 此线必须在所有event下面), 只准在腰以上的三角形里放cause. 然后用二分求到一个恰好不能再往上移了的直线, 就成了.
3. 可行性判断, 用贪心. 三角形们和直线相交的那个区间就可以代表这个三角形, 因为放在直线以上的cause都可以垂直投影到直线上, 效果更佳.
4. 在这些所有的区间中, 要找出最少的cause个数n, 使得每个区间内都能包含至少一个的cause. 如果这个n<=m, 那么这条直线ok, 否则不ok.
5. 怎么判断呢, 引用yzhw “以区间右端点为第一关键字,左端点为第二关键字进行排序,然后每次贪心的选择当前区间的右端点作为子区间,统计要导出全部区间需要子区间的个数num。” (其实第二关键字是不用排序的, 无所谓).
6. 对应5, 举个例子

---------(A)
   ------
  -------
     --------
        -------
    ------------
                 -----(B)
.....           ......

按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界<=A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面: Continue reading

[ACM] POJ 1887 2533 解题报告, LIS的nlogn算法..

记录到当前位置combo数为k的尾巴的最小值, 比如 1 3 2 6, 则 dp[combo]=tail 罗列为 dp[1]=1, dp[2]=2 (1,2的尾巴比1,3等小), dp[3]=6, combo最大为6. 然后再多加一位就看能不能更新前面combo数对应的tail, 让tail更小; 当然还看combo数能不能+1. 比如1 3 2 6再加个5, dp[3]就=5 (1,2,5的tail比1,2,6的tail小), 不加5加7就多一个dp[4]=7. 因为dp[combo]值相对于combo数是递增的, 所以可以二分查找实现nlogn.

这两个是买一送一的题目.. 1887的二分写的有点蛋疼.. 2533要求不能相等, 就加了个标记每次对二分的两个指针p0,p1, 和中点(p0+p1)/2看一下, 重复就continue, 不重复一样做, 省得麻烦.. 想了一下还可以前面严格<, 后面可以>=, 这样更新tail的时候就不会重复产生影响.

代码点下面:
Continue reading