binary search

[SPOJ] ABCDEF – ABCDEF

原题: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[] left = new int[n*n*n];
        int p = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    left[p++] = nums[i] * nums[j] + nums[k];
                }
            }
        }
        Arrays.sort(left, 0, n*n*n);
        int[][] range = new int[2][left.length];
        p = 0;
        long count = 0;
        int tmp = Integer.MAX_VALUE;
        for (int i = 0; i < left.length; i++) {
            if (tmp != left[i]){
                range[0][p] = left[i];
                range[1][p]++;
                p++;
            }
            else {
                range[1][p-1]++;
            }
            tmp = left[i];
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                for (int k = 0; k < nums.length; k++) {
                    if (nums[i] == 0)
                        continue;
                    else {
                        int right = nums[i]*(nums[j]+nums[k]);
                        int b = Arrays.binarySearch(range[0], 0, p, right);
                        if (b >= 0)
                            count+= range[1][b];
                    }
                }
            }
        }
        out.print(count);
    }

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[] left = new int[n*n*n];

int p = 0;

for (int i = 0; i < nums.length; i++) {

for (int j = 0; j < nums.length; j++) {

for (int k = 0; k < nums.length; k++) {

left[p++] = nums[i] * nums[j] + nums[k];

}

Arrays.sort(left, 0, n*n*n);

int[][] range = new int[2][left.length];

p = 0;

long count = 0;

int tmp = Integer.MAX_VALUE;

for (int i = 0; i < left.length; i++) {

if (tmp != left[i]){

range[0][p] = left[i];

range[1][p]++;

p++;

}

else {

range[1][p-1]++;

}

tmp = left[i];

}

for (int i = 0; i < nums.length; i++) {

for (int j = 0; j < nums.length; j++) {

for (int k = 0; k < nums.length; k++) {

if (nums[i] == 0)

continue;

else {

int right = nums[i]*(nums[j]+nums[k]);

int b = Arrays.binarySearch(range[0], 0, p, right);

if (b >= 0)

count+= range[1][b];

}

out.print(count);

}

Date July 30, 2015
Category SPOJ
Comments No Comments

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);

    }

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);

}

Date July 29, 2015
Category Codeforces
Comments No Comments

binary search

[SPOJ] ABCDEF – ABCDEF

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

书脊

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

Categories

Tags