佛山企业网站seo,建站快车来电,wordpress域名防封插件,兴力网站建设大家好#xff0c;我是晴天学长#xff0c;传智杯的题#xff0c;一个经典的全排列找最小的问题#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .kotori和素因子 链接#xff1a;https://ac.nowcod…大家好我是晴天学长传智杯的题一个经典的全排列找最小的问题需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .kotori和素因子 链接https://ac.nowcoder.com/acm/problem/50042 来源牛客网
输入 复制 4 12 15 28 22 输出 复制 17 说明 分别取3572可保证取出的数之和最小 示例2 输入 复制 5 4 5 6 7 8 输出 复制 -1 2) .算法思路
kotori和素因子 1.预处理2到1000的所有质数。 2.接收n个数据 3.st标记一个数只能选一个素数
dfs选数的位置 1.出口当所有数都选完了输出结果。 2.开始选数。 3.如果没有可以选的素数了返回-1. 4.递归到下一个选的数 3算法步骤
1.读取输入的行并拆分为字符串数组。
2.解析数组的第一个元素为整数n表示接下来要读取的数字个数。
3.读取下一行并将其拆分为字符串数组。
4.将字符串数组中的数字解析为整数并存储在一个整数数组num中。
5.对num数组进行排序以便后续处理。
6.调用get_primes方法预处理2到1000的质数并返回质数的个数。
7.初始化一个布尔数组st用于标记质数是否已使用。
8.调用dfs方法进行深度优先搜索初始时传入初始参数。
9.在dfs方法中如果搜索到叶子节点index length更新最小值min。
10.对于当前数字num[index]遍历质数列表list。
11.如果当前质数list.get(i)未使用且可以整除num[index]则将该质数加入当前和sum标记该质数为已使用并递归调用dfs方法。
12.在递归调用dfs方法后需要将当前质数从当前和sum中减去并将其标记为未使用。
13.如果当前数字num[index]小于质数list.get(i)则直接返回。
14.在dfs方法结束后如果最小值min仍然是初始值则输出-1否则输出最小值min。
15.实现get_primes方法使用埃氏筛法预处理2到1000的质数并将质数存储在列表list中。
16返回质数列表list的大小。 4. 代码实例
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static String[] lines;static ListInteger list new ArrayList();static boolean[] st;static int min Integer.MAX_VALUE;public static void main(String[] args) throws IOException {lines in.readLine().split( );int n Integer.parseInt(lines[0]);lines in.readLine().split( );int[] num new int[n];for (int i 0; i n; i) {num[i] Integer.parseInt(lines[i]);}Arrays.sort(num);int lenth get_primes(1000);st new boolean[lenth];dfs(st, num, 0, 0, num.length);if (min Integer.MAX_VALUE) System.out.println(-1);else System.out.println(min);}private static void dfs(boolean[] st, int[] num, int index, int sum, int length) {if (index length) {min Math.min(min, sum);return;}int temp num[index];for (int i 0; i 168; i) {if (!st[i] temp % list.get(i) 0) {sum list.get(i);st[i] true;dfs(st, num, index 1, sum, length);st[i] false;sum - list.get(i);}if (temp list.get(i)) return;}}//预处理2到1000的质数.(埃式筛)public static int get_primes(int n) {boolean[] visit new boolean[n 1];for (int i 2; i n; i) {if (!visit[i]) {list.add(i);}for (int j i i; j n; j i) {visit[j] true;}}return list.size();}
} 4.总结
回溯的正常状态一般来说dfs上下两面都是相反的。 试题链接
