题目描述
农夫约翰有 n 片连续的农田，编号依次为 1～n。
其中有 k 片农田中装有洒水器。
装有洒水器的农田的编号从小到大依次为 x1,x2,…,xk。
在某个炎热的中午，约翰觉得是时候给他的所有农田浇水了。
每个洒水器在打开以后，向两侧方向洒水，并且随着开启时间延长，有效覆盖距离也不断增长。
具体来说，我们将第 xi 片农田中的洒水器打开，经过 1 秒后，第 xi 片农田被其覆盖，经过 2 秒后，第 [xi?1,xi+1] 片农田被其覆盖，经过 j 秒后，第 [xi?(j?1),xi+(j?1)] 片农田被其覆盖。
注意，每个洒水器的有效覆盖距离在每经过整数秒后，才会有所增长。
例如，经过 2.5 秒后，被第 xi 片农田中的洒水器覆盖的农田仍是第 [xi?1,xi+1] 片农田，而不是第 [xi?1.5,xi+1.5] 片农田。
现在，约翰将所有洒水器同时打开，请问经过多少秒后，所有农田均被灌溉。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,k。
第二行包含 k 个整数 x1,x2,…,xk。
输出格式
每组数据输出一行答案。
数据范围
前三个测试点满足 1≤n≤5,
所有测试点满足 1≤T≤200，1≤n≤200，1≤k≤n，1≤xi≤n，xi?1<xi，T 组数据的 n 相加之和不超过 200。
输入样例
3
5 1
3
3 3
1 2 3
4 1
1
输出样例
3
1
4
Java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
int n = 0, k = 0, num = 0,maxLen,last, end;
for (int i = 0; i < t; i++) {
last = 0;
maxLen = Integer.MIN_VALUE;
n = scanner.nextInt();
k = scanner.nextInt();
end = n+1;
for (int j = 0; j < k; j++) {
num = scanner.nextInt();
if(j == 0){
maxLen = Math.max(num-last, maxLen);
}else{
maxLen = Math.max(((num-last)>>1)+1, maxLen);
}
last = num;
}
maxLen = Math.max(maxLen,end-num);
System.out.println(maxLen);
}
}
}
解题思路
其实就是求一个最大间隔，起始间隔为0，终止间隔为n+1，中间计算间隔是要除以2，毕竟是两个机器一起向中间灌溉。
