补种未成活胡杨

题目描述

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;
}