一天一道算法题day02
这是问题的简单版。在这个版本中，唯一的不同仅仅在 m=1m=1 。
现在，给定两个数组 a1,a2,…,ana1,a2,…,an 和 b1,b2,…,bnb1,b2,…,bn 。在进行操作前，你可以按照你的想法对这个数组进行重新排序。之后，在每一轮操作中，若数组非空，你将会进行以下两个子操作：
- 从 aa 数组中选择任意一个元素，删除它（剩余的所有元素将按照原来的相对顺序转移到一个新的 aa 数组），
- 从 bb 数组中选择任意一个元素，删除它（剩余的所有元素将按照原来的相对顺序转移到一个新的 bb 数组）。
设 kk 为两个数组的最终长度。现在，你需要找到最小的操作次数，使得对于所有的 1≤i≤k1≤i≤k ，都有 ai<biai<bi 。
由于这个问题太简单了，所以，这个问题的作者准备改进题目，让它变得更有挑战性。现在，基于前面的问题，我们再给定一个正整数 mm 。对于 mm 个数组对 (c[i],b)(c[i],b)，即 (c[1],b),(c[2],b),…,(c[m],b)(c[1],b),(c[2],b),…,(c[m],b) ，根据前面的问题要求，分别计算出它们的答案，最后，你要给出所有答案的总和。其中，1≤i≤m1≤i≤m 。注意，数组 c[i]c[i] 是从 aa 数组转化而来的。下面是关于数组 c[i]c[i] 的定义：
- c[i]1=i，
- c[i]j=aj ，其中 2≤j≤n。
输入
第一行包含一个整数 t ，表示测试样例的数量。
对于每个测试样例，第一行包含两个整数 n,m，表示数组 a,b的大小，以及元素 a1值的上限。
第二行包含 n−1 个整数 a2,…,an 。
第三行包含 n 个整数 b1,b2,…,bn 。
输出
对于每个测试样例，输出所有数组对 (ci,b)的最小操作数的总和。
样例输入
4 2 1 1 3 2 4 1 5 1 5 3 8 3 3 8 1 4 3 3 2 2 1 1 1 1 1 1 3 3 3 3 9 1 9 2 8 3 7 4 6 5 1 2 3 2 1 4 5 6 5
样例输出
0 1 4 4
提示
数据范围
对于 100%100% 的数据，保证:
1≤t≤10^4, 2≤n≤10^5, m=1, 1≤ai≤109, 1≤bi≤109。
保证所有的测试样例 n 的总和不超过 10^5 。
题目解析
这道题目要求我们找到每个数组对 (c[i],b)的最小操作次数，并最终输出这些操作次数的总和。题目通过对数组 a 和 b 进行特定操作，要求确保 ‘a[i]<b[i]‘在每一轮操作后保持成立。
问题解析
- 给定两个数组
a和b，需要从两个数组中删除元素，并保证在每轮操作后a[i] < b[i]对每个 i 成立。 - 操作次数就是每次删除的次数，最后我们要计算每个测试样例的总操作次数。
- 特别地，数组
c[i]是从a数组转化而来的，其中c[i][1] = i，而c[i][j] = a[j](对于 2≤j≤n）
解决思路
- 对于每个数组对 (c[i],b)(c[i], b)(c[i],b)，我们可以首先将
a和b排序，这样可以方便找到满足条件 ‘a[i]<b[i]‘`a[i] < b[i]`‘a[i]<b[i]‘ 的最优方案。 - 数组
a可以重新排序，找到最小的操作次数（最少删除元素的次数）使得对每个i，a[i] < b[i]成立。 - 对于数组对的数量
m，我们需要对每一个c[i]数组分别计算操作数，然后将结果相加。
代码实现
import java.util.Arrays;
import java.util.Scanner;
public class MinOperations {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt(); // 测试样例的数量
while (t-- > 0) {
int n = scanner.nextInt(); // 数组大小 n
int m = scanner.nextInt(); // m 个数组对
int[] a = new int[n - 1]; // 读取 a 数组（去掉 a1）
for (int i = 0; i < n - 1; i++) {
a[i] = scanner.nextInt();
}
int[] b = new int[n]; // 读取 b 数组
for (int i = 0; i < n; i++) {
b[i] = scanner.nextInt();
}
int totalOperations = 0; // 操作次数的总和
for (int i = 1; i <= m; i++) {
// 创建 c[i] 数组，第一个元素是 i，接下来的元素是 a 数组
int[] c = new int[n];
c[0] = i; // 第一个元素为 i
for (int j = 1; j < n; j++) {
c[j] = a[j - 1];
}
// 对 c 和 b 数组进行排序
Arrays.sort(c);
Arrays.sort(b);
// 计算最小的操作次数：使得 c[i] < b[i] 对于所有 i 成立
int operations = 0;
int bIndex = 0;
for (int cIndex = 0; cIndex < n; cIndex++) {
while (bIndex < n && c[cIndex] >= b[bIndex]) {
bIndex++; // 如果 b 数组中的数不满足条件，跳过
}
if (bIndex < n) {
bIndex++; // 匹配一个，继续下一个
} else {
operations++; // 如果不匹配，增加操作数
}
}
totalOperations += operations; // 累计操作次数
}
System.out.println(totalOperations); // 输出所有数组对的操作次数总和
}
scanner.close();
}
}