题目描述
E卷 100分题型
近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。
一个月后，有M棵胡杨未能成活。
现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
输入描述
-
N 总种植数量，1 <= N <= 100000
-
M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N
-
K 最多可以补种的数量，0 <= K <= M
输出描述
- 最多的连续胡杨棵树
示例1
输入
5
2
2 4
1
输出
3
说明
补种到2或4结果一样，最多的连续胡杨棵树都是3。
示例2
输入
10
3
2 4 7
1
输出
6
说明
种第7棵树，最多连续胡杨树棵数位6（5，6，7，8，9，10）
题解
双指针算法。 将题目思路转换为转换为线段，求最长线段所包含点的个数。
思路：
- 未存活的会将线段分成多个区间。
- 通过
补种的方式进行合并区间，记录合并之后区间的最大值。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;int main() {int n, m, k;cin >> n >> m;vector<int> notAlive(m+1,0);notAlive[m] = n+1;int index = 0;int tmp;for (int i = 0; i < m; i++){cin >> notAlive[i];}// 将未活点从小到大进行排序sort(notAlive.begin(), notAlive.end());cin >> k;int res = 0;// 左边界，代表当前区间左边存活的第一个位置int left;// 右边界代表当前区间最后一个存活的位置int right;for (int i = 0; i <= m; i++) {if (i == 0) {left = 1;} else {left = notAlive[i-1] + 1;}if (i + k >= m) {right = notAlive[m] -1;} else {right = notAlive[i+k] - 1;}res = max(res, right - left+1);}cout << res;
}
