2017微软第二场笔试题解

第一题

Queen Attack

#1497 : Queen Attack
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
There are N queens in an infinite chessboard. We say two queens may attack each other if they are in the same vertical line, horizontal line or diagonal line even if there are other queens sitting between them.

Now given the positions of the queens, find out how many pairs may attack each other?

输入
The first line contains an integer N.

Then N lines follow. Each line contains 2 integers Ri and Ci indicating there is a queen in the Ri-th row and Ci-th column.  

No two queens share the same position.  

For 80% of the data, 1 <= N <= 1000

For 100% of the data, 1 <= N <= 100000, 0 <= Ri, Ci <= 1000000000

输出
One integer, the number of pairs may attack each other.

样例输入
5  
1 1  
2 2  
3 3   
1 3
3 1
样例输出
10

题目描述

思路，一开始想到暴力枚举，时间复杂度O(n^2)这样肯定是AC不了的。所以再思考比n^2简单的方法，只有二分法O(logn)；只遍历一遍，依靠存储信息实现O(n)这两种思路。

显然二分法与本题无关。所以就是遍历一遍，利用遍历的时候存储的信息实现O(n).

思路，使用4个HashMap，分别保存每一行、每一列、每一左斜行、每一右斜行右多少个queue。只要拿到这个queue的数目，就可以计算这一行的AttackQueen对。

代码如下：

import java.util.*;
import java.util.Scanner;
    
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] x = new int[N];
        int[] y = new int[N];
        HashMap<Integer, Integer> rowMap = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> colMap = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> leftDiagonalMap = new HashMap<Integer, Integer>(); // left top to right bottom
        HashMap<Integer, Integer> rightDiagonalMap = new HashMap<Integer, Integer>();// right top to left bottom
        for (int i = 0; i < N; i++) {
            x[i] = in.nextInt();
            y[i] = in.nextInt();
            insertToMap(rowMap, x[i]);
            insertToMap(colMap, y[i]);
            insertToMap(leftDiagonalMap, x[i] - y[i]);
            insertToMap(rightDiagonalMap, x[i] + y[i]);
        }
        int res = countAttackQueue(rowMap);
        res += countAttackQueue(colMap);
        res += countAttackQueue(leftDiagonalMap);
        res += countAttackQueue(rightDiagonalMap);
        System.out.print(res);
        in.close();
    }

    public static void insertToMap(HashMap<Integer, Integer> mapping, int keyValue) {
        if (mapping.containsKey(keyValue)) {
            int tmp = mapping.get(keyValue);
            mapping.put(keyValue, tmp + 1);
        } else {
            mapping.put(keyValue, 1);
        }
        return;
    }

    public static int countAttackQueue(HashMap<Integer, Integer> mapping) {
        int res = 0;
        Iterator iter = mapping.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            int val = (int)entry.getValue();
            res += val * (val - 1) / 2;
        }
        return res;
    }
}

queen attack

第二题

Diligent Robots

#1498 : Diligent Robots
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
There are N jobs to be finished. It takes a robot 1 hour to finish one job.

At the beginning you have only one robot. Luckily a robot may build more robots identical to itself. It takes a robot Q hours to build another robot.  

So what is the minimum number of hours to finish N jobs?

Note two or more robots working on the same job or building the same robot won't accelerate the progress.

输入
The first line contains 2 integers, N and Q.  

For 70% of the data, 1 <= N <= 1000000  

For 100% of the data, 1 <= N <= 1000000000000, 1 <= Q <= 1000

输出
The minimum number of hours.

样例输入
10 1
样例输出
5

题目描述

思路，首先要证明，一部分机器人做任务，一部分机器人造机器人这种情况不会是最优解。

二分答案的思路。

start=0，end=N （end最大就是不生产机器人，直接一个机器人工作到底）

check函数，计算当前mid时间，有没有解。找到最小的有解mid即可。也就是求解 (mid - i * Q) * 2^i >= N

import java.util.*;
import java.util.Scanner;
    
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long N = in.nextLong();
        long Q = in.nextLong();
        long start = 0;
        long end = N;
        while (start + 1 <end) {
            long mid = start + (end - start) / 2;
            if (check(N, mid, Q)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        System.out.println(end);
        in.close();
        return;
    }

    public static boolean check(long N, long mid, long Q) {
        long count = mid / Q;
        if (count > 40) {
            return true;
        }
        for (long i = count; i >= 0; i--) {
            long machines = ((long)1) << i;
            if ((mid - i * Q) * machines >= N) {
                return true;
            }
        }
        return false;
    }
}

二分法

byr论坛大神的思路解法，比我自己的好，而且还按收益来证明了各种情况

/*是这样的。因为刚开始只有一个机器人，生产一个机器人的时间成本是q，生产一个机器人的收益是n/2，如果收益大于成本，那就生产机器人。第二次，有两个机器人，这两个机器人都要生产机器人，生产机器人的成本还是q，生产机器人的收益是（n/2）/2，如果收益大于成本，就生产。
给你一个通过100%的代码，你看看：
*/
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long q = sc.nextLong();
        float robot = 1;
        float gain = n;
        long time = 0;
        while (gain / 2 > q) {
            robot = robot * 2;
            gain = gain / 2;
            time += 1;
        }
        double left = Math.ceil(n / robot);
        long result = (long) (time * q + left);
        System.out.println(result);
        sc.close();
    }
/*
样例是输入10 1输出5
如果是一个机器人，不生产机器人，那么需要时间10。如果生产一个机器人，然后两个机器人一起生产，那就需要1+10/2个时间。。。。。。下面罗列了对应表
最终机器人数量：1 ->2->4->8->16->32
需要最短时间：  10->6->5->5->5->6
可以看出总时间会随着机器人的繁殖，先减少后增大。这是因为机器人过度繁殖会使生产机器人的收益减少。当收益为负时，时间就会增加，这个不难理解吧。
根据题意，另一个样例：
输入10 2输出7
1 ->2->4->8->16
10->7->7->8->9
有人会问，如果让有的机器人生产机器人，有的机器人不生产机器人，这种情况怎么办？这时可以考虑所有机器人都生产机器人，所有机器人都不生产机器人，这两种情况。那么上述情况介于后面所说的两种情况。其总时间也介于两者之间。那么这种情况就不会是最优解，一定是后两种情况中的一种是最优解。
*/

收益解法