奇安信笔试9.15

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s1 = scanner.nextLine().split(",");
        int[] pA = new int[s1.length];
        for (int i = 0; i < s1.length; i++) {
            pA[i] = Integer.parseInt(s1[i]);
        }
        String[] s2 = scanner.nextLine().split(",");
        scanner.close();
        int[] pB = new int[s1.length];
        for (int i = 0; i < s2.length; i++) {
            pB[i] = Integer.parseInt(s2[i]);
        }
        used = new boolean[pA.length + pB.length];
        int[] nums = new int[pA.length + pB.length];
        for (int i = 0; i < pA.length; i++) {
            nums[i] = pA[i];
        }
        for (int i = pA.length; i < pA.length + pB.length; i++) {
            nums[i] = pB[i - pA.length];
        }
        process(nums, nums.length / 2, 0);
        int min = Integer.MAX_VALUE;
        Set<List<Integer>> set = new HashSet<>();
        for (LinkedList<Integer> list : ret) {
            int cur = 0;
            List<Integer> a = new ArrayList<>();
            List<Integer> b = new ArrayList<>();
            for (int x : list) {
                if (x < pA.length) {
                    a.add(x);
                } else {
                    b.add(x);
                }
            }
            Collections.sort(a);
            Collections.sort(b);
            if (set.contains(a) && set.contains(b)) {
                continue;
            }
            set.add(a);
            set.add(b);
            if (a.size() >= 3) {
                int temp = 0;
                for (int z : a) {
                    temp += nums[z];
                }
                cur += temp * 0.6;
            } else {
                for (int z : a) {
                    cur += nums[z];
                }
            }
            if (b.size() >= 3) {
                int index = 0;
                int curMin = Integer.MAX_VALUE;
                for (int z : b) {
                    index++;
                    cur += nums[z];
                    curMin = Math.min(curMin, nums[z]);
                    if (index == 3) {
                        cur -= curMin;
                        curMin = Integer.MAX_VALUE;
                        index = 0;
                    }
                }
            } else {
                for (int x : b) {
                    cur += nums[x];
                }
            }
            min = Math.min(min, cur);
        }
        System.out.println(min);
    }

    static LinkedList<Integer> track = new LinkedList<>();
    static List<LinkedList<Integer>> ret = new ArrayList<>();
    static boolean[] used;

    public static void process(int[] nums, int n, int start) {
        if (track.size() == nums.length / 2) {
            ret.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            track.add(i);
            used[i] = true;
            if (i < n) {
                used[i + n] = true;
            }
            if (i >= n) {
                used[i - n] = true;
            }

            process(nums, n, start + 1);
            used[i] = false;

            if (i < n) {
                used[i + n] = false;
            }
            if (i >= n) {
                used[i - n] = false;
            }
            track.removeLast();
        }
    }
}

第二道 40%

public static int process(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        Node[] nodes = new Node[points.length];
        int index = 0;
        for (int[] nums : points) {
            nodes[index++] = new Node(nums[0], nums[1]);
        }
        Node cur = new Node(0, 0);
        return way(nodes, cur);
    }

    private static int way(Node[] nodes, Node cur) {
        Arrays.sort(nodes, new Comparator<Node>() { @Override public int compare(Node o1, Node o2) {
                return o1.x * o1.x + o1.y * o1.y - o2.x * o2.x - o2.y - o2.y;
            }
        });
        int res = 0;
        for (int i = 0; i < nodes.length; i++) {
            Node item = nodes[i];
            res += Math.abs(item.x - cur.x) + Math.abs(item.y - cur.y);
            cur = item;
        }
        return res;
    }

    private static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }