Lemonade Change
买东西, 价值5块, 一共有三种货币5,10,20. 问能不能找开. 这个遇到20$先找大的($10 + $5), 再找小的($5 x 3).
greedy
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个物品.
Educational Codeforces Round 3 A – USB Flash Drives
链接: https://codeforces.com/contest/609/problem/A 先排序一下, 然后从大往小用贪婪思想选数, 注意选的时候的两个情况有先后, 第二种情况 出现是选最后一个数的时候.
[LintCode] Best Time to Buy and Sell Stock II
public int maxProfit(int[] prices) { // write your code here int max = 0; for(int i = 1; i < prices.length; i++) { if(prices[i] – prices[i-1] > 0) max += prices[i] – prices[i-1]; } return max; }
[LintCode] Single Number
public int singleNumber(int[] A) { if (A.length == 0) { return 0; } int n = A[0]; for(int i = 1; i < A.length; i++) { n = n ^ A[i]; } return n; }
[LintCode] Majority Number
public int majorityNumber(ArrayList<Integer> nums) { // write your code int index = -1; int count = 0; for(int i = 0 ; i < nums.size(); i++) { if(count == 0) { index = i; count ++; } else { if(nums.get(i) == nums.get(index)) count++; else count–; } } return nums.get(index); }
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: public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int p = in.readInt(); IntPair[] nums = new IntPair[n]; for (int i = 0; i < nums.length; i++) { nums[i] = new IntPair(in.readInt(),i); } Arrays.sort(nums); int count […]
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开始移动尽可能多的箱子中. 因为我们已经知道时间是固定的, 所以问题转换成: 在已知时间内, 每个学生最多能拿多少箱子, 这里用贪婪的思想, 假设每个学生拿最多就可以. public void […]
Codeforces Round #310 (Div. 2) A. Case of the Zeros and Ones
原题:http://codeforces.com/contest/556/problem/A 题目大意:给一个字符串,如果出现一个0和一个1就同时消除, 问最少剩下几个. 分析: – – 0和1的个数差几个就剩下几个啊.. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int res = 0; String s = in.readLine(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ‘0’) res ++; if (s.charAt(i) == ‘1’) res –; } out.print(Math.abs(res)); }
Codeforces Round #312 (Div. 2) C. Amr and Chemistry
原题:http://codeforces.com/problemset/problem/558/C 题目大意: 给一个数组, 可以对每个数进行两个操作, *2 或者 /2. 每次操作算一步, 问一共多少步能让数组所有数都相同. 分析: 下面的code是答案, 我写的太复杂了. 一看答案那么短, 真是跪了. 答案的思路是BFS, 然后也没有什么技巧. 就是暴啊. 而且是全局暴.. 我自己的code还左移右移的写了一大堆. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] count = new int[100010];//记录从i点能走到其他点的总数 int[] visit = new int[100010];//防止环 int[] steps = new int[100010];//记录从i点走了多少步到其他点 int res = Integer.MAX_VALUE; for (int i = […]