当前位置: 首页> 健康> 母婴 > 网址你懂我意思吧在线2021_搜索引擎站长平台_2022最新新闻素材摘抄_一媒体app软件下载老版本

网址你懂我意思吧在线2021_搜索引擎站长平台_2022最新新闻素材摘抄_一媒体app软件下载老版本

时间:2025/7/9 6:52:03来源:https://blog.csdn.net/qq_45776114/article/details/145021723 浏览次数:0次
网址你懂我意思吧在线2021_搜索引擎站长平台_2022最新新闻素材摘抄_一媒体app软件下载老版本

题目描述

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;
}
关键字:网址你懂我意思吧在线2021_搜索引擎站长平台_2022最新新闻素材摘抄_一媒体app软件下载老版本

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: