1 素数拆分
一个正整数数组A
,可以把其中的某个元素A[i]
拆分成若干个和为A[i]
的数(也可以不拆分),问这个数组里最多能有多少个素数。
public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); long n = input.nextLong(); long[] nums = new long[(int) n]; long res = 0; for (long i = 0; i < nums.length; i++) nums[(int) i] = input.nextInt(); // 2 是最小的素数,全部拆成最小的素数,把个数累加。 for (long num : nums) res += num / 2; System.out.println(res); } }
2. 排列
大概意思:保持第二行输入的顺序不变,假设为数组 A,把数组 B[1..n] 与 A 的差集按递增序插入。
事后诸葛亮。
示例数据
INPUT: 5 2 4 2 OUTPUT: 1 3 4 2 5
// 归并 public class Main { public static void main(String[] args) { // 0. Some kind of bullshit. Scanner input = new Scanner(System.in); List<Integer> res = new ArrayList<>(); int n = input.nextInt(); int m = input.nextInt(); int[] A = new int[m]; // 用于存储已出现的数字 int[] B = new int[n - m]; // 用于存储未出现的数字 boolean[] C = new boolean[n + 1]; // 用于检验 A 是否出现 // 1. 获取已有的数字 [2, 1, 5] for (int i = 0; i < m; i++) { A[i] = input.nextInt(); C[A[i]] = true; } // 2. 获取剔除掉 1 中获取数字之后的数组 int k = 0; for (int i = 1; i <= n; ++i) if (!C[i]) B[k++] = i; // 3. 归并排序 int idxA = 0, idxB = 0; while (idxA < m && idxB < k) { if (A[idxA] < B[idxB]) res.add(A[idxA++]); else res.add(B[idxB++]); } // 4. 合并剩余部分 while (idxA < m) res.add(A[idxA++]); while (idxB < k) res.add(B[idxB++]); for (int i = 0; i < res.size() - 1; i++) System.out.print(res.get(i) + " "); System.out.print(res.get(res.size() - 1)); } }
3. 平分礼物
// 回溯 public class Main { private static int res; public static void main(String[] args) { Scanner input = new Scanner(System.in); int T = input.nextInt(); while (T-- > 0) { int n = input.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = input.nextInt(); res += a[i]; } dfs(a, 0, 0, 0, 0); System.out.println(res); } } /** * 递归更新最小抛弃价值 * @param a 价值数组 * @param i 价值下标 * @param first 第一个人 * @param second 第二个人 * @param delta 要抛弃的价值 */ private static void dfs(int[] a, int i, int first, int second, int delta) { if (i == a.length) { // 分完一轮之后进行判断 if (first == second) // 如果正好能够分的平均,更新最小值。 res = Math.min(delta, res); return; } dfs(a, i + 1, first + a[i], second, delta); // 把 a[i] 分给第一个人 dfs(a, i + 1, first, second + a[i], delta); // 把 a[i] 分给第二个人 dfs(a, i + 1, first, second, delta + a[i]); // 把 a[i] 扔掉 } }
全部评论
(3) 回帖