import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
//输入:有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//输入的数字先分好奇数、偶数两组
List<Integer> evenNumberList = new ArrayList<>();//偶数
List<Integer> oddNumberList = new ArrayList<>();//奇数
if(n<=1){//数据范围：1≤n≤100 （从已有的 N （ N 为偶数）个正整数中挑选），所以N>=2 ，
//输入的数据j大小满足 2≤val≤30000
}else {
for (int i = 0; i < n; i++) {
int j = sc.nextInt();
if(j%2==0){// 偶数：可以被2整除的整数
evenNumberList.add(j);
}else {
oddNumberList.add(j);
}
}
}
int evenSize = evenNumberList.size();//记录偶数个数
int count = 0;//记录素数伴侣的对数
int[] evensPartner = new int[evenSize];//记录偶数匹配的 奇数伴侣
for (Integer odd : oddNumberList ) {//奇数列表 去寻找唯一偶数
int[] used = new int[evenSize]; //用于标记这个偶数 是否 匹配伴侣 每次更换奇数伴侣都会重新更新列表。
//唯一奇数odd 在偶数列表中 寻找 未匹配的 素数伴侣。
if(find(odd,evenNumberList,used,evensPartner)){
count++; //匹配成功，总对数加一
}
}
//输出:输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
System.out.println(count);
sc.close();
}
private static boolean find(Integer odd, List<Integer> evenNumberList, int[] used, int[] evensPartner) {
for (int i = 0; i < evenNumberList.size(); i++) {
if(isPrime(odd + evenNumberList.get(i)) && used[i] == 0){
//是素数并且偶数没有被使用过
used[i] = 1;//偶数被使用，标记1。
/* 如果第i个偶数没有伴侣，或者第i个偶数原来有奇数伴侣（evensPartner[i]!=0），
并且原来的奇数伴侣能够重新找到伴侣的话(会返回true)(这里有递归调用)，则奇数odd可以设置为第i个偶数的伴侣。
这里采用了匈牙利算法：核心思想是先到先得，能让就让。
如果原来的奇数伴侣不能找到其他伴侣，则不让，每一次find都返回false。*/
if(evensPartner[i] == 0 || find(evensPartner[i], evenNumberList,used,evensPartner )){
evensPartner[i] = odd;
return true;
}
}
}
return false; // 遍历完偶数都没有可以与传入奇数做伴侣的，该奇数值没有配对的偶数
}
/*质数(prime number)又称素数，有无限个。素数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
0和1既不是质数也不是合数，最小的质数是2
* */
private static boolean isPrime(int TheSumOfOddAndEvenNumbers) {//判断这个奇数和这个偶数相加是否是素数
if(TheSumOfOddAndEvenNumbers<=1){
return false;
}else {
for (int j = 2; j < TheSumOfOddAndEvenNumbers; j++) {
if( TheSumOfOddAndEvenNumbers % j == 0){
return false;
}
}
}
return true;
}
}
/*参考引用
本系列归档至******************************************
《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html
*/
参考引用
本系列归档至******************************************
《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html
方法一（匈牙利算法）
1.解题思路
- 首先定义两个list容器，分别存储输入整数中的奇数和偶数。
- 然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得，能让就让。
- 最后输出“素数伴侣”最多时的对数。
图解展示（匈牙利算法）：
举例说明：如图所示，首先A1和B2配对（先到先得），然后轮到A2，A2也可以和B2配对，这时候B2发现A1还可以和B4配对，所以放弃了A1，选择和A2组成伴侣（能让就让）。接着A3直接和B1配对（先到先得）。最后A4尝试与B4配对，但是这样A1就只能与B2配对，而A2就找不到伴侣了，一层层递归下来，发现不可行，所以A4不能与B4配对。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
//输入:有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//输入的数字先分好奇数、偶数两组
List<Integer> evenNumberList = new ArrayList<>();//偶数
List<Integer> oddNumberList = new ArrayList<>();//奇数
if(n<=1){//数据范围：1≤n≤100 （从已有的 N （ N 为偶数）个正整数中挑选），所以N>=2 ，
//输入的数据j大小满足 2≤val≤30000
}else {
for (int i = 0; i < n; i++) {
int j = sc.nextInt();
if(j%2==0){// 偶数：可以被2整除的整数
evenNumberList.add(j);
}else {
oddNumberList.add(j);
}
}
}
int evenSize = evenNumberList.size();//记录偶数个数
int count = 0;//记录素数伴侣的对数
int[] evensPartner = new int[evenSize];//记录偶数匹配的 奇数伴侣
for (Integer odd : oddNumberList ) {//奇数列表 去寻找唯一偶数
int[] used = new int[evenSize]; //用于标记这个偶数 是否 匹配伴侣 每次更换奇数伴侣都会重新更新列表。
//唯一奇数odd 在偶数列表中 寻找 未匹配的 素数伴侣。
if(find(odd,evenNumberList,used,evensPartner)){
count++; //匹配成功，总对数加一
}
}
//输出:输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
System.out.println(count);
sc.close();
}
private static boolean find(Integer odd, List<Integer> evenNumberList, int[] used, int[] evensPartner) {
for (int i = 0; i < evenNumberList.size(); i++) {
if(isPrime(odd + evenNumberList.get(i)) && used[i] == 0){
//是素数并且偶数没有被使用过
used[i] = 1;//偶数被使用，标记1。
/* 如果第i个偶数没有伴侣，或者第i个偶数原来有奇数伴侣（evensPartner[i]!=0），
并且原来的奇数伴侣能够重新找到伴侣的话(会返回true)(这里有递归调用)，则奇数odd可以设置为第i个偶数的伴侣。
这里采用了匈牙利算法：核心思想是先到先得，能让就让。
如果原来的奇数伴侣不能找到其他伴侣，则不让，每一次find都返回false。*/
if(evensPartner[i] == 0 || find(evensPartner[i], evenNumberList,used,evensPartner )){
evensPartner[i] = odd;
return true;
}
}
}
return false; // 遍历完偶数都没有可以与传入奇数做伴侣的，该奇数值没有配对的偶数
}
/*质数(prime number)又称素数，有无限个。素数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
0和1既不是质数也不是合数，最小的质数是2
* */
private static boolean isPrime(int TheSumOfOddAndEvenNumbers) {//判断这个奇数和这个偶数相加是否是素数
if(TheSumOfOddAndEvenNumbers<=1){
return false;
}else {
for (int j = 2; j < TheSumOfOddAndEvenNumbers; j++) {
if( TheSumOfOddAndEvenNumbers % j == 0){
return false;
}
}
}
return true;
}
}
方法二（利用io流）
1.解题思路思路和方法一基本一致，不同的是通过io流操作来处理输入的数据。
2.代码实现
import java.io.*;
import java.util.ArrayList;
public class Main{
static int max=0;
public static void main(String[] args) throws Exception{
//io输入
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
while((s=br.readLine())!=null){
//输入正偶数n
int n=Integer.parseInt(s);
//输入n个整数
String[] arr=br.readLine().split(" ");
//用于存储所有的奇数
ArrayList<Integer> odds=new ArrayList<>();
//用于存储所有的偶数
ArrayList<Integer> evens=new ArrayList<>();
for(int i=0;i<n;i++){
int num=Integer.parseInt(arr[i]);
//将奇数添加到odds
if(num%2==1){
odds.add(num);
}
//将偶数添加到evens
if(num%2==0){
evens.add(num);
}
}
//下标对应已经匹配的偶数的下标，值对应这个偶数的伴侣
int[] matcheven=new int[evens.size()];
//记录伴侣的对数
int count=0;
for(int j=0;j<odds.size();j++){
//用于标记对应的偶数是否查找过
boolean[] v=new boolean[evens.size()];
//如果匹配上，则计数加1
if(find(odds.get(j),matcheven,evens,v)){
count++;
}
}
System.out.println(count);
}
}
//判断奇数x能否找到伴侣
private static boolean find(int x,int[] matcheven,ArrayList<Integer> evens,boolean[] v){
for(int i=0;i<evens.size();i++){
//该位置偶数没被访问过，并且能与x组成素数伴侣
if(isPrime(x+evens.get(i))&&v[i]==false){
v[i]=true;
/*如果i位置偶数还没有伴侣，则与x组成伴侣，如果已经有伴侣，并且这个伴侣能重新找到新伴侣，
则把原来伴侣让给别人，自己与x组成伴侣*/
if(matcheven[i]==0||find(matcheven[i],matcheven,evens,v)){
matcheven[i]=x;
return true;
}
}
}
return false;
}
//判断x是否是素数
private static boolean isPrime(int x){
if(x==1) return false;
//如果能被2到根号x整除，则一定不是素数
for(int i=2;i<=(int)Math.sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
}
京公网安备 11010502036488号