题解 | #素数伴侣#

这题我是硬想出来的，感觉原理挺简单的，重点在把题目的模型抽象出来。

我们可以把题目理解为：

给你一张无向图，每找出一条边就删除这条边以及它的两个端点，让你找出最多的边。

那这就简单了。我来说说我的思路：

准备工作

首先是准备工作。因为输入的数字在2到30000之间，所以两数相加的和最多在4到60000之间。准备一个容器来存储这些素数，一会直接用contains方法找就行。

具体方法就不写了，有个小技巧就是如果除数遍历到了这个数的(int)平方根了，还不能整除，那这个被除数肯定是素数，直接省一半时间复杂度。

构建模型

然后就要开始建模了，这里基于贪心策略，所以建议所有容器使用红黑树作为底层。

1).先把每个输入的数做成一个结点，包含数的值和它的子结点集合children。子节点的含义就是和它成对的结点们。用来表示图中的边。

2).再做一个容器set，用来表示整个图中的所有结点，方便后面遍历。

3).遍历，把每个结点的子结点集合赋值，如果该结点的子结点集合中有元素，放入容器。

4).从set中挑出子结点最少（连线最少）的那个结点x，再从x的子结点中挑出子结点最少的结点y。从set、children中删除这两个结点。这样就从无向图中删掉了“影响最小”的两个结点。

5)

重复4，直至set中没有结点或set中的结点的children都没有子结点。

以下是代码。感觉用Map做更好些，懒得重构了，大概意思是这样。

import java.util.*;

/**
 * @author FunnelCakes
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //制作素数集合，3到60000全部素数
        Set<Integer> primeSet = new TreeSet<>();
        for (int i = 4; i < 60000; i++) {
            boolean flag = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                primeSet.add(i);
        }

        while (scanner.hasNext()) {
            //读入
            int n = scanner.nextInt();//第一行,n
            int[] vals = new int[n];//第二行，n个正整数
            for (int i = 0; i < n; i++) {
                vals[i] = scanner.nextInt();
            }
            List<PointNode> pointNodeList = new ArrayList<>();
            for (int val : vals) {
                pointNodeList.add(new PointNode(val));
            }
            //结点匹配，构建无向图
            PointNodeSet pointNodeSet = new PointNodeSet(new PointNodeComparator());
            for (PointNode pointNode : pointNodeList) {
                for (PointNode pointNode1 : pointNodeList) {
                    if (pointNode.val != pointNode1.val) {
                        int plus = pointNode.val + pointNode1.val;
                        if (primeSet.contains(plus)) {
                            pointNode.children.add(pointNode1);
                        }
                    }
                }
                if (!pointNode.children.isEmpty()) {
                    pointNodeSet.add(pointNode);
                }
            }
            //成对移除pointNodeSet，删除边
            int count = 0;
            while (!pointNodeSet.isEmpty()) {
                PointNode pointNode1 = pointNodeSet.first();
                if (pointNode1.children.isEmpty()) {
                    pointNodeSet.remove(pointNode1);
                } else {
                    PointNode pointNode2 = pointNode1.children.first();
                    pointNodeSet.removeSide(pointNode1, pointNode2);
                    count++;
                }
            }

            System.out.println(count);
            break;
        }
    }
}

//以下是模型，写得稀碎，别骂了别骂了。。
class PointNodeSet extends TreeSet<PointNode> {
    private static PointNodeComparator pointNodeComparator;

    public PointNodeSet(Comparator<? super PointNode> comparator) {
        super(comparator);
    }

    @Override
    public Comparator<? super PointNode> comparator() {
        return new PointNodeComparator();
    }

    //删除边
    public boolean removeSide(PointNode o1, PointNode o2) {

        if (o1 == null || o2 == null)
            return false;
        /*System.out.println(this.remove(o1));
        System.out.println(this.remove(o2));*/
        PointNodeSet tmpSet = new PointNodeSet(new PointNodeComparator());

        for (PointNode pointNode : this) {
            if (!pointNode.equals(o1) && !pointNode.equals(o2)) {
                pointNode.children.remove(o1);
                pointNode.children.remove(o2);
                tmpSet.add(pointNode);
            }
        }
        this.clear();
        this.addAll(tmpSet);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        PointNode obj = (PointNode) o;
        if (o == null)
            return false;
        Iterator<PointNode> iterator = this.iterator();
        boolean flag = false;
        while (iterator.hasNext()) {
            if (iterator.next().val == obj.val) {
                flag = true;
                iterator.remove();
                break;
            }
        }
        return flag;

    }
}

class PointNode {
    public int val;
    public PointNodeSet children;

    public PointNode(int val) {
        this.val = val;
        this.children = new PointNodeSet(new PointNodeComparator());
    }


}

class PointNodeComparator implements Comparator<PointNode> {


    @Override
    public int compare(PointNode o1, PointNode o2) {

        if (o1.children.size() == o2.children.size())
            return -1;
        return o1.children.size() - o2.children.size();
    }
}