前言综述：

本次od机试考试一共三道题，第一道题和第二道题各100分，第三道题200分。本次考试的答案都是2.5h考试的时候写的，代码写的也许并不好。在考试中还是蛮紧张的，所以写代码的时候注重的是完成考试，对于时间复杂度和空间复杂度的优化没有做过考虑。还是建议大家考试前多刷刷牛客网的试题，我大概刷了39道题，很多时候一道题我能思考三四天。同一类型题只要一次理解了，基本上就可以举一反三。如果你们看完这几道题的答案，你们会发现，1和3题解法用的是一类。希望这些能帮到后面有需要的兄弟，我是个小白，但是心里也想着做一些有反馈的事情给到大家。

目录

前言综述：

第一题

题目描述

输入描述：

输出描述：

第一题考试的源代码答案如下：

输入：

输出：

说明：

第二题

题目描述

输入描述：

输出描述：

第二题考试的源代码答案如下：

输入：

输出：

第三题

题目描述

输入描述：

输出描述：

第三题考试的源代码答案如下：

输入：

输出：

---

第一题

题目描述

疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。黑板上已经写了N个正整数，同学们需要给每个数分别上一种颜色。为了让黑板报即没关又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这N个数进行上色。

输入描述：

第一行有一个正整数N，其中1<=N<=100。

第二行有N个int型数（保证输入数据在[1,100]范围中），表示黑板上各个正整数的值。

输出描述：

输入只有一个整数，为最少需要的颜色种数。

第一题考试的源代码答案如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int[] array = new int[n];
			for (int i = 0; i < n; i++) {
				array[i] = sc.nextInt();
			}
			// 先对数组进行排序，方便遍历
			Arrays.sort(array);
			// 记录最少需要的颜色数量
			int count = 0;
			int[] s = new int[n];
			for (int i = 0; i < n; i++) {
				if (s[i] > 0) {
					continue;
				} else {
					for (int j = i; j < n; j++) {
						if ((array[j] % array[i]) == 0) {
							s[j]++;
						}
					}
					count++;
				}
			}
			System.out.println(count);
		}
	}
}

输入：

3

2 4 6

输出：

1

说明：

所有数都能被2整除

第二题

题目描述

有一个N个整数的数组，和一个长度为M的窗口，窗口从数组内的第一个数开始滑动直到窗口不能滑动为止，每次窗口滑动产生一个窗口和（窗口内所有数和和），求窗口滑动产生的所有窗口和的最大值。

输入描述：

第一行输入一个正整数N，表示整数个数。（0<N<100000）

第二行输入N个整数，整数的取值范围为[-100,100]。

第三行输入一个正整数M，M代表窗口大小，M<=100000，且M<=N。

输出描述：

窗口滑动产生的所有窗口和的最大值。

第二题考试的源代码答案如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int[] array = new int[n];
			for (int i = 0; i < n; i++) {
				array[i] = sc.nextInt();
			}
			// 生成一个新数组，记录窗口大小m。
			int m = sc.nextInt();
			int[] arrM = new int[n - m + 1];
			for (int i = 0; i < n - m + 1; i++) {
				arrM[i] = 0;
				for (int j = 0; j < m; j++) {
					arrM[i] += array[i + j];
				}
//				System.out.println(arrM[i]);
			}
			// 排序，取出最后一个最大的值
			Arrays.sort(arrM);
			System.out.println(arrM[n - m]);

		}

	}

}

输入：

6

10 20 30 15 23 12

3

输出：

68

第三题

题目描述

入职后，导师会请你吃饭，你选择了火锅。

火锅里会在不同时间下很多菜。

不同食材要煮不同的时间，才能变得刚好合适。你希望吃到最多的刚好合适的菜，但你的手速不够快，用m代表手速，每次下手捞菜后至少要过m庙才能在捞（每次只能捞一个）。

那么用最合理的策略，最多能吃到多少刚好合适的菜？

输入描述：

第一行两个整数n，m，其中n代表往锅里下的菜的个数，m代表手速。

接下来有n行，每行有两个数x，y代表第x秒下的菜过y秒才能变得刚好合适。

（1 < n, m < 1000）

（1 < x, y < 1000）

输出描述：

输出一个整数代表用最合理的策略，最多能吃到刚好合适的菜的数量

第三题考试的源代码答案如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[] x = new int[n];
			int[] y = new int[n];
			for (int i = 0; i < n; i++) {
				x[i] = sc.nextInt();
				y[i] = sc.nextInt();
			}
			// 设置一个数组，存放每道菜可以吃到的时间。
			int[] arrTime = new int[n];
			for (int i = 0; i < n; i++) {
				arrTime[i] = x[i] + y[i];
			}
			// 对数组进行从小到大进行排序，这样便于后面比较计算
			Arrays.sort(arrTime);

			// 新建一个数组，和数组arrTime对应，用于记录每道菜是否可以吃到，可以吃到标记加1.
			int[] arrCount = new int[n];

			int next = 0;
			arrCount[0] = 1;
			for (int i = 1; i < n; i++) {
				if (arrTime[i] >= (arrTime[next] + m)) {
					arrCount[i] = 1;
					next = i;
				}
			}

			int count = 0;
			for (int i = 0; i < n; i++) {
				if (arrCount[i] > 0) {
					count++;
				}
			}

			// 遍历输出结果
//			for (int a : arrCount) {
//				System.out.println(a);
//			}

			System.out.println(count);
		}

	}
}

输入：

2 1

1 2

2 1

输出：

1