奇安信笔试9.15
第一道超时 过了25%
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;
}
} 
