题解 | #车站建造问题#

题意整理

数轴上有n个点，这n个点必须建立收集站。
如果这n个点之间，相邻两个点间隔不是素数，则必须在中间修建对应数量的收集站，使得所有间隔是素数。
求需要建设的收集站的最少数量。

方法一（欧拉筛+动态规划）

1.解题思路

首先计算给定n个特殊点的最大间隔距离，最大距离记为max。
然后通过欧拉筛统计1到max间的素数，然后动态规划求每个距离需要的站点数。
状态定义： $dp[i]$ 表示对应间隔需要建多少个站点。
状态初始化:如果是素数，则不需建站点，初始为0。
状态转移：如果不是素数，先将状态置为最大的int型整数。枚举每一个间隔，要么修改当前站点数的站点，要么减去对应间隔状态的站点数加一，两者取较小值。

由于题目数据量过大，运行超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int work (int n, int[] a) {
        //求最大的相邻收集站间隔
        int max=-1;
        for(int i=1;i<n;i++){
            max=Math.max(max,a[i]-a[i-1]);
        }

        //初始化dp数组，dp[i]表示对应间隔需要建多少个站点
        int[] dp=new int[max+1];
        //素数标记数组
        boolean[] prime=getPrime(max);

        for(int i=1;i<=max;i++){
            //如果是素数，不需要额外站点
            if(prime[i]){
                dp[i]=0;
            }
            //如果不是素数，根据之前状态，统计所需最少站点数
            else{
                dp[i]=Integer.MAX_VALUE;
                for(int j=1;j<=i/2;j++){
                    dp[i]=Math.min(dp[i],dp[i-j]+1);
                }
            }
        }

        //将所需站点添加到结果变量
        int res=n;
        for(int i=1;i<n;i++){
            int dist=a[i]-a[i-1];
            if(!prime[dist]){
                res+=dp[dist];
            }
        }
        return res;
    }

    //欧拉筛统计1到n之间所有素数
    private boolean[] getPrime(int n) {
        boolean[] res=new boolean[n+1];
        //本题中1当素数看待
        res[1]=true;
        //flag用于标记检测出的合数，如果为0，则说明没有标记为合数，是素数
        int[] flag=new int[n+1];
        int[] prime =new int[n+1];
        //目前统计出的素数数量
        int count=0;
        for(int i =2;i<=n;i++) {
            if(flag[i]==0){
                prime[count++]=i;
                res[i]=true;
            }
            //当前数字i乘以之前统计出的素数，作为合数标记出来
            for(int j=0;j<count&&i*prime[j]<=n;j++) {
                flag[prime[j]*i]=1;
            }
        }

        return res;        
    }    
}

3.复杂度分析

时间复杂度：假设相邻站点最大间隔为d，求dp数组过程总共有两层循环，所以最终的时间复杂度是 $O(d^2)$ 。
空间复杂度：假设相邻站点最大间隔为d,需要额外大小为d+1的dp数组以及标记数组，所以空间复杂度是 $O(d)$ 。

方法二（哥德巴赫猜想）

1.解题思路

前置知识：

哥德巴赫猜想：任一大于2的偶数，都可表示成两个素数之和。（引自维基百科）
回到本题中，当相邻间隔不是素数时，如果这个数是偶数，则可以拆成两个素数；如果这个数是奇数（记为n），有两种情况，一种是n-2是素数，那么它可以直接拆分成2和n-2，即拆成2个素数，另一种是n-2不是素数，那么可以拆成1和n-1，而n-1（偶数）一定可以拆成两个素数，即总共拆成3个素数。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int work (int n, int[] a) {
        //初始化结果
        int res=n;
        for(int i=1;i<n;i++){
            int d=a[i]-a[i-1];
            //如果间隔不是素数，新增对应站点数
            if(!isPrime(d)){
                res+=segment(d);
            }
        }
        return res;
    }

    //判断是否是素数
    private boolean isPrime(int x){
        //本题中1也当作素数
        if(x==1) return true;
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }

    //哥德巴赫猜想
    private int segment(int d){
        if(d%2==0){
            return 1;
        }
        else{
            if(isPrime(d-2)){
                return 1;
            }
            else{
                return 2;
            }
        }
    }
}

3.复杂度分析

时间复杂度：假设相邻站点最大间隔为d，最坏情况下，每次判断素数需要 $图片说明$ 的时间复杂度，需要判断n次，所以最终的时间复杂度是 $图片说明$ 。
空间复杂度：不需要额外的空间，所以空间复杂度是 $O(1)$ 。