补种未成活胡杨-北京尧图网络

一、题目题目描述近些年来我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨编号1-N排成一排。一个月后有M棵胡杨未能成活。现可补种胡杨K棵请问如何补种只能补种不能新种可以得到最多的连续胡杨树输入描述N 总种植数量1 N 100000M 未成活胡杨数量M 个空格分隔的数按编号从小到大排列1 M NK 最多可以补种的数量0 K M输出描述最多的连续胡杨棵树示例1输入522 411234输出31说明补种到2或4结果一样最多的连续胡杨棵树都是3。示例2输入1032 4 711234输出61说明种第7棵树最多连续胡杨树棵数位65678910解题思路这道题目主要是考察如何通过补种胡杨树使得胡杨树形成【最长的连续序列】。示例解释示例1输入522 411234解释胡杨树总共有 5 棵编号分别是 1, 2, 3, 4, 5。未成活的胡杨树编号是 2 和 4。只能补种 1 棵树。选择补种位置可以补种编号为2的树得到序列 1, 2, 3最多连续 3 棵树。或者补种编号为4的树得到序列 3, 4, 5同样可以得到最多连续 3 棵树。因此输出结果为 3。示例2输入1032 4 711234解释胡杨树总共有 10 棵编号分别是 1 到 10。未成活的胡杨树编号是 2, 4, 7。只能补种 1 棵树。选择补种位置如果补种编号为7的树可以形成最长连续序列 5, 6, 7, 8, 9, 10连续的胡杨树棵数为 6。其他补种选择如2或4得到的最长连续胡杨树棵数较少。因此输出结果为 6。代码思路基本与下题一致最大连续1的个数 III参考题解https://leetcode.cn/problems/max-consecutive-ones-iii/solutions/608931/zui-da-lian-xu-1de-ge-shu-iii-by-leetcod-hw12/双指针解法容易理解二、代码# 读取胡杨树的总数Ntotalint(input())# 读取未成活胡杨树的数量Mdead_countint(input())# 读取未成活胡杨树的编号列表dead_listlist(map(int,input().split()))# 读取可以补种的胡杨树数量Ksupplement_countint(input())# 初始化数组所有树最初都是成活的0表示成活1表示未成活nums[0]*total# 根据输入将未成活的树的位置标记为1fornumindead_list:nums[num-1]1# 树的编号从1开始因此需要减1# 初始化滑动窗口的左右边界left0max_len0# 用于存储最大连续成活区域的长度sum_left0# 滑动窗口左边界的未成活树数量sum_right0# 滑动窗口右边界的未成活树数量# 遍历所有的树right代表滑动窗口的右边界forrightinrange(total):sum_rightnums[right]# 更新右边界的未成活树数量# 如果窗口内的未成活树数量大于可以补种的数量whilesum_right-sum_leftsupplement_count:sum_leftnums[left]# 缩小窗口左边界右移left1# 更新最大成活区域的长度max_lenmax(max_len,right-left1)# 输出最大连续成活区域的长度print(max_len)算法解析滑动窗口/双指针问题转化将 N 棵胡杨的成活状态成活0未成活1视为一个二进制数组nums。题目转化为在最多允许将 K 个 1 翻转为 0即补种 K 棵未成活树的条件下求数组中最长的连续 0 的子数组长度。滑动窗口维护left和right分别表示窗口的左右边界初始均为0。sum_right记录从数组开头到当前右边界right包含的未成活树即1的总数前缀和。sum_left记录从数组开头到左边界left之前即[0, left-1]区间的未成活树总数前缀和。这样窗口[left, right]内实际的未成活树数量为sum_right - sum_left。窗口扩张与收缩右指针right每次向右移动一位并更新sum_right。当窗口内未成活树数量(sum_right - sum_left)超过可补种数量K时说明窗口内需要补种的树太多了超过了限额此时需要收缩左边界left直到条件再次满足即移出一些未成活的树减少需要补种的数量。收缩时sum_left会累加被移出窗口的树的状态nums[left]。更新答案在每一步有效的窗口即窗口内未成活树数量 ≤ K中计算窗口长度right - left 1并更新全局最大值max_len。结果最终的max_len即为通过补种最多 K 棵树能获得的最长连续成活胡杨序列的长度。该算法时间复杂度为 O(N)空间复杂度为 O(N)用于存储状态数组可以高效处理 N 最大为 100000 的数据规模。说明

补种未成活胡杨

相关推荐

[光学原理与应用-504]：T‑MINI PLUS激光雷达测距，如何避免被相连的雷达测距发出的激光干扰

基于AKShare构建AI金融数据技能：量化交易与智能投研的数据基石

使用SteamCMD在Windows上搭建Unturned服务器的完整实战指南

更多资讯

AI Agent的算力底座：从多轮调用到高效并发治理

6GB显存跑决策模型：Kev与Laya量化部署实践全解析

降AI率实战：10款工具测评与5步改写工作流

6GB显存跑双本地模型：OOM避坑与GGUF量化部署实录

Agent新底座：算力竞争下半场的架构重构与落地实践

OpenCLAW与Codex本地AI工具链部署指南

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？