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 solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int m = in.readInt();
        int[] nums = IOUtils.readIntArray(in, n);
        long t = n;
        for (int i = 0; i < nums.length; i++) {
            t += nums[i];
        }
        long l = 2; // at least 2
        long r = t; // most
        while (l < r) {
            long mid = l + (r - l) / 2;
            int[] tmp = nums.clone();
            int index = n - 1;
            for (int i = 0; i < m; i++) {
                while (index >= 0 && tmp[index] == 0)
                    index--;
                long pos = mid - index - 1; // ith person in last pile's possible times of move
                if (pos <= 0)
                    break;
                while (index >= 0 && tmp[index] <= pos) {
                    pos -= tmp[index]; // take all boxes of the index
                    index--;
                }
                if (index >= 0) { // remove already moved box for current index
                    tmp[index] -= pos;
                }
            }
            if (index < 0)
                r = mid - 1;
            else
                l = mid + 1;
        }
        out.print(r);

    }