贪心
引题
给定一个有序数组arr，代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n-1]。给定一个正数L，代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
思路
1. 以数组中第一个点为绳子的开头，往后一个一个遍历，看能够覆盖多少个点。以第二个点为开头，往后依次遍历，记录覆盖的点的个数，依次遍历，寻找最大值。
2. 采用二分思想，当数组中每个点都为绳子的结尾，绳子长度为L时，寻找开头的位置。如arr[3]=9，L=9，寻找>=arr[3]-L 的最左边的点的位置。
3. 以A为开头，最后一个不超过L的位置为结尾B，以第一个点为A，找满足条件的最远的B的位置，然后将A往前移动一个位置，B从当前位置继续往下遍历，寻找满足的结尾。
代码
import java.util.Arrays;public class Code01_CordCoverMaxPoint {public static int maxPoint1(int[] arr, int L) {int res = 1;for (int i = 0; i < arr.length; i++) {int nearest = nearestIndex(arr, i, arr[i] - L);res = Math.max(res, i - nearest + 1);}return res;}public static int nearestIndex(int[] arr, int R, int value) {int L = 0;int index = R;while (L <= R) {int mid = L + ((R - L) >> 1);if (arr[mid] >= value) {index = mid;R = mid - 1;} else {L = mid + 1;}}return index;}public static int maxPoint2(int[] arr, int L) {int left = 0;int right = 0;int N = arr.length;int max = 0;while (left < N) {while (right < N && arr[right] - arr[left] <= L) {right++;}max = Math.max(max, right - (left++));}return max;}// for testpublic static int test(int[] arr, int L) {int max = 0;for (int i = 0; i < arr.length; i++) {int pre = i - 1;while (pre >= 0 && arr[i] - arr[pre] <= L) {pre--;}max = Math.max(max, i - pre);}return max;}// for testpublic static int[] generateArray(int len, int max) {int[] ans = new int[(int) (Math.random() * len) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = (int) (Math.random() * max);}Arrays.sort(ans);return ans;}public static void main(String[] args) {int len = 100;int max = 1000;int testTime = 100000;for (int i = 0; i < testTime; i++) {int L = (int) (Math.random() * max);int[] arr = generateArray(len, max);int ans1 = maxPoint1(arr, L);int ans2 = maxPoint2(arr, L);int ans3 = test(arr, L);if (ans1 != ans2 || ans2 != ans3) {System.out.println("oops!");break;}}}}
随堂练习
数轴上有 N 个点，求一条长度为 K 的线段最多覆盖多少个点？，此处我们认为长度为1的线段最多可以覆盖1个点。
数据范围：1≤n≤30000，1≤k≤1000
数据描述：
第一行N和K，表示点数和线段长度
第二行N个数，表示N个点的坐标
输出描述：
输出一个数，最多覆盖的点数
示例1
输入
5 3
1 2 3 4 5
输出
3
示例2
输入
5 3
1 3 5 7 9
输出
2
Java代码
import java.util.Scanner;
import java.util.Arrays;public class Main {public static int maxPoint(int[] arr, int L) {int left = 0;int right = 0;int N = arr.length;int max = 0;while (left < N) {while (right < N && arr[right] - arr[left] < L) {right++;}max = Math.max(max, right - (left++));}return max;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int l = sc.nextInt();int [] arr = new int [n];for(int i = 0 ; i < n ; i++){arr[i] = sc.nextInt();}System.out.println(maxPoint(arr, l));}}
C++代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;int main()
{int n;int k;cin>>n>>k;int w[100010];for(int i = 0; i < n; i++)cin>>w[i];int l = 0;int m = 0;for(int i=0; i<n; i++){while(w[i]-w[l]>=k){l++;}m = max(m,i-l+1);}cout<<m<<endl;;return 0;
}Python代码
n,k= input().split()
n=int(n)
k=int(k)
N=input().split()
ln=len(N)
l=0
m=0
for i in range(0,ln):while int(N[i])-int(N[l])>=k:l+=1m=max(m,i-l+1)
print(m)
贪心
引题
给定一个有序数组arr，代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n-1]。给定一个正数L，代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
思路
1. 以数组中第一个点为绳子的开头，往后一个一个遍历，看能够覆盖多少个点。以第二个点为开头，往后依次遍历，记录覆盖的点的个数，依次遍历，寻找最大值。
2. 采用二分思想，当数组中每个点都为绳子的结尾，绳子长度为L时，寻找开头的位置。如arr[3]=9，L=9，寻找>=arr[3]-L 的最左边的点的位置。
3. 以A为开头，最后一个不超过L的位置为结尾B，以第一个点为A，找满足条件的最远的B的位置，然后将A往前移动一个位置，B从当前位置继续往下遍历，寻找满足的结尾。
代码
import java.util.Arrays;public class Code01_CordCoverMaxPoint {public static int maxPoint1(int[] arr, int L) {int res = 1;for (int i = 0; i < arr.length; i++) {int nearest = nearestIndex(arr, i, arr[i] - L);res = Math.max(res, i - nearest + 1);}return res;}public static int nearestIndex(int[] arr, int R, int value) {int L = 0;int index = R;while (L <= R) {int mid = L + ((R - L) >> 1);if (arr[mid] >= value) {index = mid;R = mid - 1;} else {L = mid + 1;}}return index;}public static int maxPoint2(int[] arr, int L) {int left = 0;int right = 0;int N = arr.length;int max = 0;while (left < N) {while (right < N && arr[right] - arr[left] <= L) {right++;}max = Math.max(max, right - (left++));}return max;}// for testpublic static int test(int[] arr, int L) {int max = 0;for (int i = 0; i < arr.length; i++) {int pre = i - 1;while (pre >= 0 && arr[i] - arr[pre] <= L) {pre--;}max = Math.max(max, i - pre);}return max;}// for testpublic static int[] generateArray(int len, int max) {int[] ans = new int[(int) (Math.random() * len) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = (int) (Math.random() * max);}Arrays.sort(ans);return ans;}public static void main(String[] args) {int len = 100;int max = 1000;int testTime = 100000;for (int i = 0; i < testTime; i++) {int L = (int) (Math.random() * max);int[] arr = generateArray(len, max);int ans1 = maxPoint1(arr, L);int ans2 = maxPoint2(arr, L);int ans3 = test(arr, L);if (ans1 != ans2 || ans2 != ans3) {System.out.println("oops!");break;}}}}
随堂练习
数轴上有 N 个点，求一条长度为 K 的线段最多覆盖多少个点？，此处我们认为长度为1的线段最多可以覆盖1个点。
数据范围：1≤n≤30000，1≤k≤1000
数据描述：
第一行N和K，表示点数和线段长度
第二行N个数，表示N个点的坐标
输出描述：
输出一个数，最多覆盖的点数
示例1
输入
5 3
1 2 3 4 5
输出
3
示例2
输入
5 3
1 3 5 7 9
输出
2
Java代码
import java.util.Scanner;
import java.util.Arrays;public class Main {public static int maxPoint(int[] arr, int L) {int left = 0;int right = 0;int N = arr.length;int max = 0;while (left < N) {while (right < N && arr[right] - arr[left] < L) {right++;}max = Math.max(max, right - (left++));}return max;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int l = sc.nextInt();int [] arr = new int [n];for(int i = 0 ; i < n ; i++){arr[i] = sc.nextInt();}System.out.println(maxPoint(arr, l));}}
C++代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;int main()
{int n;int k;cin>>n>>k;int w[100010];for(int i = 0; i < n; i++)cin>>w[i];int l = 0;int m = 0;for(int i=0; i<n; i++){while(w[i]-w[l]>=k){l++;}m = max(m,i-l+1);}cout<<m<<endl;;return 0;
}Python代码
n,k= input().split()
n=int(n)
k=int(k)
N=input().split()
ln=len(N)
l=0
m=0
for i in range(0,ln):while int(N[i])-int(N[l])>=k:l+=1m=max(m,i-l+1)
print(m)