蓝桥杯刷题——day3

题目一

题干

每张票据有唯一的 ID 号，全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。你的任务是通过编程，找出断号的 ID 和重号的 ID。数据保证断号不可能发生在最大和最小号。
输入格式：
一个整数 N(N<100) 表示后面数据行数，接着读入N行数据，每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于10的5次方），每个整数代表一个 ID 号。
输出格式：
要求程序首先输入要求程序输出1 行，含两个整数m，n，用空格分隔，其中，m表示断号 ID，n表示重号 ID。
示例一：

输入：
2
5 6 8 11 9
10 12 9
输出：
7 9

示例二：

输入：
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
输出：
105 120

题目链接：错误票据

题目解析

这道题目挺有意思的，其实不难，输入部分我们就不过多介绍，我们可以创建一个Arraylist用作存储，没输入一个数字，就将数字存储到Arraylist中去，然后用排序，将Arraylist从小到大进行排序，从后往前遍历，当发现两个数字相等的时候则该数字就是重复的ID，当发现两个数字相差大于1的时候就发现该数字为丢失的数字。下面为完整代码：

代码

import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入行数int line = scanner.nextInt();ArrayList<Integer> list = new ArrayList<>();// 读取所有 IDfor (int i = 0; i < line; i++) {while (scanner.hasNextInt()) {list.add(scanner.nextInt());}}// 排序 IDCollections.sort(list);// 找出断号和重号int missing = 0, duplicate = 0;for (int i = 1; i < list.size(); i++) {if (list.get(i).equals(list.get(i - 1))) {duplicate = list.get(i); // 找到重号} else if (list.get(i) > list.get(i - 1) + 1) {missing = list.get(i - 1) + 1; // 找到断号}}// 输出结果System.out.println(missing + " " + duplicate);}
}

题目二

题干

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1，当石头的高度下降到0时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到0 是允许的)。小青蛙一共需要去学校上x 天课，所以它需要往返2x 次。当小青蛙具有一个跳跃能力y 时，它能跳不超过y 的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式：
输入的第一行包含两个整数n,x, 分别表示河的宽度和小青蛙需要去学校的天数。请注意2x 才是实际过河的次数。第二行包含n−1 个非负整数 表示在河中与 小青蛙的家相距i的地方有一块高度为h的石头，h=0则表示没有石头。
输出格式：
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
示例一：

输入：
5 1
1 0 1 0
输出：
4

题目链接：青蛙过河

题目解析

这是一个典型的二分查找加模拟的问题。小青蛙需要在有限的石头高度和跳跃能力的限制下完成往返 2x 次。以下是解决问题的详细思路：

1. 最小跳跃能力y 的范围是从 1 到n，我们可以用二分查找找到最小的y，使得小青蛙能够完成2x 次过河。
2. 给定一个跳跃能力y，模拟小青蛙的跳跃过程，检查是否能完成2x 次过河。然后每次跳跃时，石头高度减 1，不能跳到高度为 0 的石头上。
3. 判断是否满足条件的方法用模拟实现。如果当前 y 能够完成2x 次过河，则尝试更小的 y；否则增加 y。

下面是完整代码：

代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入河宽度和需要去学校的天数int n = scanner.nextInt();int x = scanner.nextInt();// 输入石头高度int[] stones = new int[n];for (int i = 1; i < n; i++) {stones[i] = scanner.nextInt();}// 二分查找最低跳跃能力int left = 1, right = n, result = n;while (left <= right) {int mid = (left + right) / 2;if (canCross(stones.clone(), mid, 2 * x)) {result = mid; // 当前跳跃能力可行，尝试更小值right = mid - 1;} else {left = mid + 1; // 当前跳跃能力不足，增加跳跃能力}}// 输出结果System.out.println(result);}// 判断是否能完成指定次数的过河public static boolean canCross(int[] stones, int jump, int trips) {int n = stones.length;for (int t = 0; t < trips; t++) {int position = 0; // 从起点出发while (position < n - 1) {int next = position;// 找到能跳到的最远位置for (int j = position + 1; j < n && j <= position + jump; j++) {if (stones[j] > 0) {next = j;}}if (next == position) {// 无法前进，跳跃失败return false;}// 跳到 next，石头高度减 1stones[next]--;position = next;}}return true; // 成功完成所有 trips}
}

main函数其实很好理解就是一个二分查找的问题，我们看canCross函数，在这个函数模拟小青蛙从起点出发，经过石头跳到对岸的过程。外层循环 for (int t = 0; t < trips; t++)循环模拟小青蛙过河的过程。因为小青蛙需要往返2x 次，所以我们要模拟trips 次跳跃，while (position < n - 1)循环则检查小青蛙是否跳到了对岸，for (int j = position + 1; j < n && j <= position + jump; j++) 循环则是找小青蛙能跳到的最远距离，当我们发现next == position时，就表明小青蛙一动不动，也就是跳跃失败，否则石头的高度减去1，并且更新position。这段代码我并没有完全通过编译器，其出现的问题我也不太清楚，如果发现问题，欢迎私信和评论，感谢各位的点赞。