Menu Sidebar
Menu

greedy

[LintCode] Best Time to Buy and Sell Stock II

[LintCode] Single Number

[LintCode] Majority Number

Codeforces Round #Pi (Div. 2) C. Geometric Progression

原题: http://codeforces.com/contest/567/problem/C 题目大意: 给一个n大小数组, 问其中的子序列(非连续)能组成多少个已p为公比的等比序列, 且长度为3. 分析: 这题卡了好久, 我用找等差数列的方法改的. 后来总是过不了test. 可是怎么看我的是O(nlgn)的复杂度, 所以过不了大的test case 肯定是有O(n)的. 于是开始想啊想啊….最后想到了是用等比中项的性质. 首先上一个过不了的code:

最后看了一下答案, 发现是用两个set保存当前数字为等比中项的前后序列, 然后记录一下相同项的个数. 第二次扫描的时候, 如果当前数字能整除公比, 那么找到j,i,k的个数,相乘就是答案. 这里注意要用long存. 难怪我test老挂 答案code:

 

Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes

原题:http://codeforces.com/contest/551/problem/C 题目大意: n堆箱子, m个学生要搬走箱子, 每个学生走过在箱子中间移动需要一秒, 移除一个箱子需要一秒, 问最少多少秒搬完. 分析: 这题有两个很tricky的地方. 一个是在搬走的时候, 不需要移动学生到别的地方. 所以如果学生在箱子上面, 在n秒内, 就能搬走n个箱子. 第二个是学生之间是同步进行搬箱子的. 解题的时候, 用的是穷举, 后来过不了TLE了. 看了答案才明白是二分搜索问题. 这里二分搜索用的是以下的原理: 如果在t秒内能完成任务, 那么肯定在大于t秒的时间内也能完成. 这就说明我们可以忽略那些大于t秒的情况.如何找到t呢. 因为题中告诉我们: at least one pile is non empty. 所以移动到这个non-empty pile需要1秒, 移动box 需要1秒, 所以我们的low bound是2. 那high bound是什么? 我们假设只有一个学生, 移动到n个地方需要n秒, 移除a1,a2…an个箱子需要a1+a2….+an秒, 所以high bound是(数组长度+box总数). 所以我们的range是在[2,Total(box+index)] 在每次搜索中,我们对m个学生依次分配任务, 从最后一个non-empty的pile开始移动尽可能多的箱子中. 因为我们已经知道时间是固定的, 所以问题转换成: 在已知时间内, 每个学生最多能拿多少箱子, 这里用贪婪的思想, 假设每个学生拿最多就可以.

Codeforces Round #310 (Div. 2) A. Case of the Zeros and Ones

原题:http://codeforces.com/contest/556/problem/A 题目大意:给一个字符串,如果出现一个0和一个1就同时消除, 问最少剩下几个. 分析: – – 0和1的个数差几个就剩下几个啊..

Codeforces Round #312 (Div. 2) C. Amr and Chemistry

原题:http://codeforces.com/problemset/problem/558/C 题目大意: 给一个数组, 可以对每个数进行两个操作, *2 或者 /2. 每次操作算一步, 问一共多少步能让数组所有数都相同. 分析: 下面的code是答案, 我写的太复杂了. 一看答案那么短, 真是跪了. 答案的思路是BFS, 然后也没有什么技巧. 就是暴啊. 而且是全局暴.. 我自己的code还左移右移的写了一大堆.

书脊

倾城与倾国, 佳人难再得