2018商汤笔试题

摘苹果

有N堆苹果，每堆苹果有x,y,w三个属性，每次能够进行的操作是：把一堆苹果移动到另一堆苹果中，移动苹果所需要花费的力气为$w imes (|x_1-x_2|+|y_1-y_2|$ ,问最少需要花费多少力气才能把这些苹果移动到一堆去？

暴力解法复杂度为$O(n^2)$,问题等价于寻找一个中心点。
这个问题关键在于距离的定义比较特殊。如果距离定义为欧式距离，这个问题就变得非常艰难（比如费马点），这是一个NP问题。
因为距离定义比较特殊，所以x方向和y方向是完全无关的。可以分开考虑这两者。首先把这个问题看做一维来考虑。

引题
一条路上分布着N个村庄，每个村庄都有一个坐标，现在要在这条路上修建一个水站，使得这N个村庄到水站的距离之和最短。
这个问题的结论是：把水站建立在中位数上。如果村庄个数为奇数个，那么正好有一个中位数；如果村庄个数为偶数个，那么水站建立在中间两个村庄之间。

回到本题中来，因为x和y是无关的，所以可以先求出最优的x和最优的y。这样一来，把全部苹果移动到x,y处是最恰当的，但是只能把苹果移动到有苹果的点，所以只能找x,y附近的一些点，这是因为整个二维平面是一个凸面，必然只有一个最小点。只需要枚举离中间点最近的几个点即可，这么做当然是不严谨的。很容易举出反例来。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
final int MAXN = (int) (1e5 + 7);
 
class Point {
    long x, y, w;
 
    Point(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }
}
 
Point find(Point[] a, long total) {
    int cnt = 0;
    long half = total >> 1;
 
    for (Point i : a) {
        cnt += i.w;
        if (cnt >= half) {
            return i;
        }
    }
    return a[a.length - 1];
}
 
Main() {
    Scanner cin = new Scanner(System.in);
    int N = cin.nextInt();
    Point[] a = new Point[N];
    long total = 0;
    for (int i = 0; i < N; i++) {
        a[i] = new Point(cin.nextInt(), cin.nextInt(), cin.nextInt());
        total += a[i].w;
    }
    Arrays.sort(a, Comparator.comparingInt(m -> (int) (m.x)));
    long x = find(a, total).x;
    Arrays.sort(a, Comparator.comparingInt(m -> (int) (m.y)));
    long y = find(a, total).y;
    Arrays.sort(a, Comparator.comparingInt(m -> (int) (Math.abs(m.x - x) + Math.abs(m.y - y))));
    long ans = Long.MAX_VALUE;
    for (int j = 0; j < Math.min(50, N); j++) {
        long s = 0;
        for (Point i : a) {
            s += i.w * (Math.abs(i.x - a[j].x) + Math.abs(i.y - a[j].y));
        }
        ans = Math.min(ans, s);
    }
    System.out.println(ans);
}
 
 
public static void main(String[] args) {
    new Main();
}
}

狙击手

N个狙击手，每个狙击手瞄准一个人（这个人有可能是他自己！）。所有狙击手不会同时开枪。你可以随意安排所有狙击手开枪的次序，直到无法再开枪为止，问：经过一番厮杀之后，最多幸存几个狙击手、最少幸存几个狙击手？

这个问题是两问：一问是狙击手最多活几个，一问是狙击手最少活几个。
一眼看上去，狙击手之间构成的结构是图。而实际上，这个图非常特殊：每个狙击手只能瞄准一个人，所以每个结点的出度必然是1，而入度可以很多。

首先考虑最多幸存几个狙击手。很显然，那些未被瞄准的人必然会幸存下来。但是这些人是一定要开枪的。这些“必然不死者”乱枪过后，会拯救一批新的“必然不死者”，“必然不死者”开枪之后又会拯救不死者，这样一直到全部“不死者”都无法开枪为止。所以这个问题可以用优先队列来解决：优先让必然不死者开枪（他们是一定要开枪的）。

接下来考虑最少幸存几个狙击手。这就需要深刻理解这个问题的特殊之处：每个结点出度为1。需要看清楚“单出度图”的一个特点：如果含有环，只能是形如“0”和形如“6”这样的环，不可能出现形如“8”的环。而每个形如6的环最少幸存一个人。于是，问题转化为：整个图中有多少个“6”。

import java.util.*;

public class Main {
class Node {
    int id, cnt;

    Node(int id, int cnt) {
        this.id = id;
        this.cnt = cnt;
    }
}

int nonzero(boolean died[]) {
    int s = 0;
    for (int i = 1; i < died.length; i++) {
        if (!died[i]) s++;
    }
    return s;
}

Main() {
    Scanner cin = new Scanner(System.in);
    int N = cin.nextInt();
    int a[] = new int[N + 1];
    int b[] = new int[N + 1];//bi表示想杀i的人的个数
    for (int i = 1; i <= N; i++) {
        a[i] = cin.nextInt();
    }
    for (int i = 1; i <= N; i++) b[a[i]]++;
    PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparing(x -> x.cnt));
    for (int i = 1; i <= N; i++) {
        q.add(new Node(i, b[i]));
    }
    boolean died[] = new boolean[N + 1];
    for (int i = 1; i <= N; i++) if (a[i] == i) died[i] = true;
    while (!q.isEmpty()) {
        int now = q.poll().id;
        if (died[now]) continue;
        if (!died[a[now]]) {
            died[a[now]] = true;
            int next = a[a[now]];//我的下下家得到解放
            b[next]--;
            q.add(new Node(next, b[next]));
        }
    }
    int maxLive = nonzero(died);
    Arrays.fill(died, false);
    for (int i = 1; i <= N; i++) if (a[i] == i) died[i] = true;
    int ring[] = new int[N + 1];//ring i是否在环上
    for (int i = 1; i <= N; i++) ring[i] = i;
    for (int i = 1; i <= N; i++) {
        if (died[i]) continue;
        int now = i;
        while (!died[a[now]] && a[now] != i) {
            died[a[now]] = true;
            now = a[now];
        }
        if (a[now] == i) {//如果成环了，要让环的祖先承担后续损失
            int j = i;
            while (true) {
                ring[j] = i;
                j = a[j];
                if (j == i) break;
            }
        }
        if (ring[a[now]] != a[now]) {
            died[ring[a[now]]] = true;
        }
    }
    int minLive = nonzero(died);
    System.out.println(minLive);
    System.out.println(maxLive);
}


public static void main(String[] args) {
    new Main();
}
}

最小区间

给定K个长度为N的数组，要求一个最小区间（区间长度尽量小），要求这个最小区间包含的数字跟K个数组中任一数组的交集都不为空。

优先队列+单调队列很容易处理。

import java.util.*;

public class Main {
class Point {
    int x, k, index;

    Point(int x, int k, int index) {
        this.x = x;
        this.k = k;
        this.index = index;
    }
}

Main() {
    Scanner cin = new Scanner(System.in);
    int K = cin.nextInt();
    int N = cin.nextInt();
    PriorityQueue<Point> q = new PriorityQueue<>(Comparator.comparing(x -> x.x));
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < N; j++) {
            int x = cin.nextInt();
            q.add(new Point(x, i, j));
        }
    }
    int[] inqCount = new int[K];
    Queue<Point> qq = new LinkedList<>();//单调队列
    int nonzeroCount = 0;
    int ans = Integer.MAX_VALUE;
    int beg = 0, end = 0;
    boolean startCheck = false;//是否开始覆盖
    while (!q.isEmpty()) {
        Point now = q.poll();
        qq.add(now);
        inqCount[now.k]++;
        if (inqCount[now.k] == 1) {
            nonzeroCount++;
            if (nonzeroCount == K) {
                startCheck = true;
            }
        }
        //弹出无用元素
        while (!qq.isEmpty() && inqCount[qq.peek().k] > 1) {
            inqCount[qq.peek().k]--;
            qq.poll();
        }
        if (startCheck) {
            int minValue = qq.peek().x;
            int nowAns = now.x - minValue;
            if (nowAns < ans) {
                ans = nowAns;
                beg = minValue;
                end = now.x;
            }
        }
    }
    System.out.println(beg + " " + end);
}

public static void main(String[] args) {
    new Main();
}
}