近些年来，我国防沙治沙取得显著成果。某沙漠新种植 棵胡杨（编号 - ），排成一排。
一个月后，有 棵胡杨未能成活。
现可补种胡杨 棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
总种植数量，
未成活胡杨数量
个空格分隔的数，按编号从小到大排列，
最多可以补种的数量，
最多的连续胡杨棵树
5
2
2 4
1
3
补种到2或4结果一样，最多的连续胡杨棵树都是3。
10
3
2 4 7
1
6
补种第7棵树，最多连续胡杨树棵数位6（5，6，7，8，9，10）
首先，我们需要找出最长的连续胡杨树范围，这个范围可以通过计算两棵未成活胡杨树之间的距离得到。在得到这个距离之后，我们可以根据补种的数量进行判断。如果补种的数量足够将整个范围的未成活胡杨树都补上，那么最长连续胡杨树范围就是该距离。否则，我们可以将所有可补种的胡杨树全部补上，最长连续胡杨树范围就是原来的距离减去未补种的胡杨树数量。
考虑到我们还需要处理数组两端的情况，所以在实现上需要将补种的情况分成三种来处理：
此算法的时间复杂度是O(m)，其中m是未成活胡杨树的数量。这是因为我们只需要遍历一次未成活胡杨树数组，所以时间复杂度为线性级别。
空间复杂度是O(m)，我们使用一个数组来存储所有的未成活胡杨树，所以空间复杂度也是线性级别的。
虽然这个算法看起来复杂度较高，但由于N和M的取值范围有限，该算法在实际应用中的性能是可接受的。
#include <stdio.h>
int solution(int n, int m, int* indies, int k) {
int maxLen = 0;
for (int i = 0; i <= m - k; i++) {
if (i == 0) {
maxLen = indies[i + k] > maxLen ? indies[i + k] - 1 : maxLen;
} else if (i == m - k) {
maxLen = n - indies[i - 1] > maxLen ? n - indies[i - 1] : maxLen;
} else {
maxLen = indies[i + k] - indies[i - 1] - 1 > maxLen ? indies[i + k] - indies[i - 1] - 1 : maxLen;
}
}
return maxLen;
}
int main() {
int n, m, k;
scanf("%d %d", &n, &m);
int indies[m];
for (int i = 0; i < m; i++) {
scanf("%d", &indies[i]);
}
scanf("%d", &k);
printf("%d\n", solution(n, m, indies, k));
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
int solution(int n, int m, std::vector<int> indies, int k) {
int maxLen = 0;
for (int i = 0; i <= m - k; i++) {
if (i == 0) {
maxLen = std::max(maxLen, indies[i + k] - 1);
} else if (i == m - k) {
maxLen = std::max(maxLen, n - indies[i - 1]);
} else {
maxLen = std::max(maxLen, indies[i + k] - indies[i - 1] - 1);
}
}
return maxLen;
}
int main() {
int n, m, k;
std::cin >> n >> m;
std::vector<int> indies(m);
for (int i = 0; i < m; i++) {
std::cin >> indies[i];
}
std::cin >> k;
std::cout << solution(n, m, indies, k) << std::endl;
return 0;
}
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
*
* @Author: Amos
* @E-mail: amos@amoscloud.com
* @Date: 2023/8/1
* @Time: 14:15
* @Description:
*/
public class Main0256 {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int N = scanner.nextInt();
int M = scanner.nextInt();
int[] indies = new int[M];
for (int i = 0; i < M; i++) {
indies[i] = scanner.nextInt();
}
int K = scanner.nextInt();
System.out.println(solution(N, M, indies, K));
}
}
public static int solution(int n, int m, int[] indies, int k) {
int maxLen = 0;
for (int i = 0; i <= m - k; i++) {
if (i == 0) {
maxLen = Math.max(maxLen, indies[i + k] - 1);
} else if (i == m - k) {
maxLen = Math.max(maxLen, n - indies[i - 1]);
} else {
maxLen = Math.max(maxLen, indies[i + k] - indies[i - 1] - 1);
}
}
return maxLen;
}
}
def solution(n, m, indies, k):
max_len = 0
for i in range(m - k + 1):
if i == 0:
max_len = max(max_len, indies[i + k] - 1)
elif i == m - k:
max_len = max(max_len, n - indies[i - 1])
else:
max_len = max(max_len, indies[i + k] - indies[i - 1] - 1)
return max_len
n, m = map(int, input().split())
indies = list(map(int, input().split()))
k = int(input())
print(solution(n, m, indies, k))
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
})
let input = []
readline.on('line', line => input.push(line))
readline.on('close', () => {
const [n, m] = input[0].split(' ').map(Number)
const indies = input[1].split(' ').map(Number)
const k = Number(input[2])
let maxLen = 0
for (let i = 0; i <= m - k; i++) {
if (i === 0) {
maxLen = Math.max(maxLen, indies[i + k] - 1)
} else if (i === m - k) {
maxLen = Math.max(maxLen, n - indies[i - 1])
} else {
maxLen = Math.max(maxLen, indies[i + k] - indies[i - 1] - 1)
}
}
console.log(maxLen)
})
package main
import (
"fmt"
)
func solution(n int, m int, indies []int, k int) int {
maxLen := 0
for i := 0; i <= m-k; i++ {
if i == 0 {
if indies[i+k]-1 > maxLen {
maxLen = indies[i+k] - 1
}
} else if i == m-k {
if n-indies[i-1] > maxLen {
maxLen = n - indies[i-1]
}
} else {
if indies[i+k]-indies[i-1]-1 > maxLen {
maxLen = indies[i+k] - indies[i-1] - 1
}
}
}
return maxLen
}
func main() {
var n, m, k int
fmt.Scan(&n, &m)
indies := make([]int, m)
for i := range indies {
fmt.Scan(&indies[i])
}
fmt.Scan(&k)
fmt.Println(solution(n, m, indies, k))
}