NC586 题解 | #车站建造问题#

题意分析

在一个一维坐标轴上面需要给出n个必须建造车站的点的位置，但是要求任意相邻两个车站之间的距离要么是1，要么是素数，问至少需要建造多少个车站？

思路分析

首先，给出的n个点必须要建造车站，但是相邻任意两个点之间的距离可能过大。我们不方便直接枚举，也似乎很难枚举。这里，我们抛出一个定理。这似乎是我们从高中就知道的一个顶顶有名的猜想，就是歌德巴赫猜想：任意大于2的偶数都可以写成两个素数的和。这个证明我就不证明了，当然，我也证明不了。
我们继续分析题目，所以对于某一段距离，如果这段距离是素数，那么我们不进行处理，否则，如果是偶数，那么就可以拆分成两个素数的和，如果是奇数，那么可以拆分成2和一个奇数，如果这个奇数是素数，那么这样是最优的，否则，就可以将这个奇数拆分成一个素数和一个偶数，这个偶数可以猜分成三个素数。
至于还有一种优化的写法，利用线性筛预处理出来的方法进行处理，我写了几个版本都是内存超限，所以这种方法应该是不可行的。
综上
- 两点之间的距离是偶数，分成两个素数，中间建造一个车站。
- 两点之间的距离是奇数，是否可以分成2+素数，可以，中间建造一个车站，不可以，拆分成三个素数。

alt

复杂度分析
- 需要对给出的点进行遍历，同时对于每个间隔，我们需要判断是否为素数，这里的时间复杂度为 $O(\sqrt{m})$ ，m为最大的间隔。所以总的时间复杂度为 $O(n\sqrt{m})$
- 过程中只用了少数几个数组，空间复杂度为 $O (1)$

C++版本

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    bool judge(int x){
        if(x==1) return true;
        for(int i=2;i*i<=x;i++){
            if(x%i==0) return false;
        }
        
        return true;
    }
    int work(int n, int* a, int aLen) {
        // write code here
        int ans=aLen;
        for(int i=1;i<aLen;i++){
            int len=a[i]-a[i-1];
            // 如果中间距离是素数
            if(!judge(len)){
                // 如果中间距离不是素数同时使偶数
                if(len%2==0) ans++;
                else{
                    // 如果中间距离不是素数而且是奇数，但是这个奇数可以拆分成2+素数
                    if(judge(len-2)) ans++;
                    // 如果只能分为奇素数+偶数
                    else ans+=2;
                }
            }
        }
        
        return ans;
    }
};

Go版本

package main

/**
  * 
  * @param n int整型 
  * @param a int整型一维数组 
  * @return int整型
*/
// 判断是否为1或者素数
func judge(x int) bool{
    if(x==1){
        return true
    }
    
    for i := 2; i*i <= x; i++{
        if(x%i==0){
            return false
        }
    }
    
    return true
}
func work( n int ,  a []int ) int {
    // write code here
    ans := n
    for i := 1; i < n; i++ {
        len :=a[i]-a[i-1] 
        // 如果这个间隔不是素数
        if(!judge(len)){
            // 同时不是偶数
            if(len%2==1){
                // 是否可以拆分成2+素数
                if(judge(len-2)){
                    ans++
                }else{
                    // 拆分成奇素数+偶数
                    ans+=2
                }
            }else{
                // 偶数的情况
                ans++
            }
        }
    }
    
    return ans
}