车站建造问题

[编程题]车站建造问题

热度指数：14361 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

X轴上10^8个点，从左到右依次编号为0~10^8-1，相邻点距离为1，其中有n个点有特殊意义，从小到大依次为a₀~a_n-1，其中保证a₀=0.

现在需要建设收集站，有两个要求必须被满足：
1、每个有意义的点必须修建收集站。
2、相邻收集站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设收集站的最小数量。

示例1

输入

3,[0,7,11]

输出

说明

在0,7,8,11处建造收集站，差值分别为7,1,3，符合要求

备注:

输入数据包含一个数n和一个长度为n的数组a，数组a的下标为0~n-1，保证a数组递增，且a₀=0。
输出一个整数，表示答案。
1<=n<=1000，a数组中数值保证小于10^8

算法知识视频讲解

Java

牛客600767110号

我感觉我的输出没问题

用例:
8,[0,1,4,11,12,21,22,29]
对应输出应该为:
9
你的输出为:
10

[0, 1, 3, 7, 1, 7, 1, 1, 1, 7]

发表于 2020-07-24 19:12:59 回复(0)

Java

Fubuki_0v0

public int work (int n, int[] a) {
int c=0;
for(int i=0; i<n-1; i++) {
c+=getNum(a[i+1]-a[i]);
}
return n + c;
}

private int getNum (int len) {
if(isPrime(len)) { //两站间距是质数，不用在中间修站点
return 0;
} else {
if(len%2 == 0) { //两站间距非质数，是偶数，根据哥德巴赫猜想，大于2的偶数可写成两质数之和
return 1;
} else {
if(isPrime(len-2)) { //因为2是唯一的偶数质数，所以任一奇数不可能拆分为两个非2的质数相加
//两站间距非质数，是奇数，想要中间只修一个站，只有拆分为2+（len-2）
return 1;
}
return 2; //两站间距非质数，是奇数，且间距大于5（len=1，2，3，4，5都到不了这里）
//根据强哥德巴赫猜想，任一大于5的奇数都可写成三个质数之和
//此情况亦可认为是拆分为 1+（len-1），len-1为偶数，参考哥德巴赫猜想
}
}
}

private boolean isPrime (int n) {
for(int i=2; i<=Math.sqrt(n); i++) {
if(n%i==0) {
return false;
}
}
return true;
}

编辑于 2020-06-14 02:38:04 回复(0)

Java

牛客255098966号

计算中间站点，参考上面大神们的思路，感谢各位大神的分享，我就给个中间判断的部分解释

private int between(int num) {
        if (isPrime(num) || num == 1)
            // 1 和 素数 中间不需要站点
            return 0;
        else if ((num & 1) == 0)
            // 哥德巴赫猜想： 任一大于2的偶数，都可表示成两个素数之和， 需要一个连接站点
            return 1;
        else if (isPrime(num - 2))
            // 大于二的偶数部分分采用哥德巴赫猜想，
            // 奇数部分采用孪生素数猜想和强哥德巴赫猜想
            // 孪生素数猜想： 存在无穷多个素数P，使得P+2是素数，            
            // 孪生素数猜想使得站点间减小到1，即优于强哥德巴赫猜想的2（针对本题），
            // 所以优先于强哥德巴赫猜想
            return 1;
        else
            // 强哥德巴赫猜想: 任一大于5的奇数都可写成三个素数之和, 需要两个连接站点
            return 2;

    }

发表于 2020-06-12 18:32:41 回复(0)

Java

随缘学习法

哥德巴赫猜想被证明了吗？

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int work (int n, int[] a) {
        int res=1;
        for(int i=1; i<a.length;i++){
            if (iemzhishu(a[i]-a[i-1])){
                res++;
            }
            else if ((a[i]-a[i-1])%2==0||iemzhishu(a[i]-a[i-1]-2)){
                res=res+2;
            }
            else{
                res=res+3;
            }
            
            
        }
       return res;
    }
    public boolean iemzhishu(int b){
        for (int i=2;i<=Math.sqrt(b);i++){
            if(b%i==0){
                return false;
            }
           
        }
        return true;
    }
}

编辑于 2020-06-05 14:11:47 回复(0)

Java

最爱小怪兽

根据前排的思路，提供java版本

import java.util.*;

public class Solution {
   public int work(int n, int[] a) {
		int res=1;
		for (int i = 1; i < n; i++) {
			int disance=a[i]-a[i-1];
			if(isPrime(disance)) {
				res++;
			}else if(disance%2==0||isPrime(disance-2)){
				res+=2;
			}else{
				res+=3;
			}
		}
		return res;
	}

	public boolean isPrime(int n) {
		for (int i = 2; i <= Math.sqrt(n + 0.0); i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

发表于 2020-06-02 22:15:15 回复(0)