原题:http://www.spoj.com/problems/ABCDEF/ 题目大意:计算一个集合S,范围在[-30000,30000], 其中所有的可能的整数abcdef. 满足: (a*b+c)/d-e=f, where d !=0. 问多少种情况 分析: 公式题, 首先是整数取值, 所以就不难.先化简成a*b+c=d(e+f), 然后数一下左边集合中每个在右边的的个数. 注意: 这里是每个元素, 包括重复的. SPOJ真是卡空间, 用map直接TLE, 好好自己写counter吧. d不能是0 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = in.readInt(); } Arrays.sort(nums); int[] […]
原题: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 […]