Menu Sidebar
Menu

binary search

Educational Codeforces Round 3 D – Gadgets for dollars and pounds

链接: https://codeforces.com/contest/609/problem/D 这题好tricky, 好几个test都是c++的ll类型的, java做着好头疼. 首先根据题意可以看出来, 能在x天完成任务(从m中买到k个item), 在剩下的x+1天也能完成, 所以具有单调性, 可以在排序(根据买东西的实际价格排序, 这里的实际价格是第i天的汇率*单价). 其次我们的目标是买k个东西, 那么如果给定某天x, 如何用同样的钱(假设), 买更多的东西?, 肯定是先买便宜的啊. 所以是贪心算法. 既然是贪心算法, 我们就要找到算法的关键, 那就是如何在m天中的第i天买到更便宜的东西? 显然, 我们知道汇率和单价是乘法关系, 就要分别找到前i天的两种货币的最低汇率minD和minP, 然后我们要测试一下在cur天的时候, 我们能否买够所需的k个物品. 这里我们用minD和minP分别乘以m个物品, 然后得到的价格就是cur天实际价格, 然后通过排序并且提取前k个物品, 我们就可以测试能否在cur天购买到k个物品.

First Bad Version

 

H-Index II

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections

原题: http://codeforces.com/contest/574/problem/A 题目大意: 给一个n的数的数组, 问如何让第一个数拿最少数组中别的数字的数,使得第一个数变成这个数组最大的数. 分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是O(n2), 看来能有lgn的做法. 后来想想, 假设第一个数是数组中最大的数, 那么就可以不用拿别的数, 如果第一个数不是数组中最大的数, 那么它最多拿的数, 应该是数组中最大的数. 假设数组: 5 1 11 2 8. 第一个数5不是数组中最大的数字, 那么我们可以假设, 最坏情况下, 我们最多拿11(11为数组中最大的数字), 使得5变成数组中最大的数字, 当然这个情况是最坏情况. 其次, 上面例子中的5 1 11 2 8的结果是4, 那么我们可以证明, 任何大于4的数字都是可以的. 因此, 我们可以通过二分搜索的办法, 搜索这个数字. 复杂度是o(nlgn), n是每次检查搜索结果的正确性, lg是二分.

[LintCode] Copy Books

[LintCode] Search a 2D Matrix

[SPOJ] DIVSUM – Divisor Summation

原题: http://www.spoj.com/problems/DIVSUM/ 题目大意: 给一个数n,找到它所有的除数的合. 比如number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22. 分析: 第一次提交的时候, 老老实实找每个divisor, 结果tle了. 后来想想20/2 = 10, 一次可以把2和10都找到, 所以lgn就可以有. 先上第一次代码:

以上代码tle, 下面是二分代码:

另外注意的是, 1的结果是….0….

[SPOJ] NOTATRI – Not a Triangle

原题:http://www.spoj.com/problems/NOTATRI/ 题目大意:给一个数组, 找到其中不能组成三角形的3-tuple的个数. 分析:睡前A一道. 简单的计算. 两边之和<第三边, 先排序一下数组, 然后把第三边取数组最后一个, 也是最大一个数. 然后两个指针left和right, meet in middle, 个数是 right-left, 因为每次当满足条件时, 所有在right和left中的元素, 都可以看成以当前i为第三边和当前的left为一条边时, 移动right往left靠拢,这些可能的组合, 都是满足条件的, 因为right靠谱left是一个递减的过程.

[SPOJ] FACVSPOW – Factorial vs Power

原题:http://www.spoj.com/problems/FACVSPOW/ 题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n 分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code

可是tmd怎么也过不了. 后来想想是二分搜索, 首先, 假设n可以满足, 那么n+1肯定满足. 所以我们可以用二分搜索每次忽略一半. 其次就是怎么计算fact. 翻书啊,翻书 翻到了Stirlings Approximation, 真是简便的公式: . 然后就是low bound就是2*a吧, 但是high bound是啥啊…我数学不好, 真的算不出来. 就靠试数了..反正spoj也没提交限制…

 

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

November 2019
M T W T F S S
« Oct    
 123
45678910
11121314151617
18192021222324
252627282930