A problem description

Second algorithm design

1 If the number of stones removed is equal to the total number of stones (M=N), enter L directly.

2 Add the start (0) and end (N+1) stones, and the distances to the start node are 0 and L, respectively.

3 Sort all stones according to the distance from the starting node from small to large.

4 Let left=0, right=L, if right-left>1, then mid=(right+left)/2, determine whether it is satisfied that after removing M stones, any distance is less than mid.If it is satisfied, it means that the distance can be larger, let left = mid; otherwise, let right = mid, and continue the binary search.

5 After the search, left is the maximum value of the shortest distance that the cow must jump.

Three codes

package com.platform.modules.alg.alglib.poj3258;import java.util.Arrays;public class Poj3258 {public String output = "";private final int maxn = 50050;private Integer L;private Integer n;private Integer m;private Integer dis[] = new Integer[maxn];public Poj3258() {for (int i = 0; i < dis.length; i++) {dis[i] = 0xFFFFFFF;}}public String cal(String input) {String[] line = input.split("\n");String[] line1 = line[0].split(" ");L = Integer.parseInt(line1[0]);n = Integer.parseInt(line1[1]);m = Integer.parseInt(line1[2]);if (n == m) {return L.toString();}for (int i = 1; i <= n; i++) {dis[i] = Integer.parseInt(line[i]);}dis[0] = 0; // Increment start pointdis[n + 1] = L; // add end pointArrays.sort(dis, 0, n + 1);//sort(dis, dis + n + 2);Integer left = 0;Integer right = L;while (right - left > 1) {int mid = (right + left) / 2;if (judge(mid))left = mid;//If it can be released, it means that x can be largerelseright = mid;}return left.toString();}boolean judge(int x) { //After removing m stones, any distance is not less than xint num = n - m; //Remove m stones, place num stones, loop num timesint last = 0; //Record the index of the previous placed stonefor (int i = 0; i < num; i++) { //For these stones, make any spacing not less than xint cur = last + 1;while (cur <= n && dis[cur] - dis[last] < x) //Place the first position with a distance >=x from lastcur++; //accumulate position by curif (cur > n)return false; //If it is greater than n during this process, it means that it cannot be releasedlast = cur; //Update the last position}return true;}}

Four tests