题目描述与示例
题目描述
近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。
一个月后，有M棵胡杨未能成活。
现可补种胡杨K棵，请问如何补种（只能补种，不能新种) ,可以得到最多的连续胡杨树?
题目练习网址：https://www.algomooc.com/problem/P3254
输入描述
[code]N`：总种植数量 `1> M; // 未成活胡杨的位置 vector trees(M); for (int i = 0; i < M; i++) { cin >> trees; } // 补种数目 int K; cin >> K; // 初始化平铺数组，初始化均为1 vector nums(N, 1); // 遍历所有死树 for (int i = 0; i < M; i++) { // trees是死树从1到N的编号 // trees-1是死树在数组中从0到N-1的索引 nums[trees - 1] = 0; } // 初始化左指针为0，初始化窗口中包含的0的个数为0，初始化答案为0 int left = 0; int win_0 = 0; int ans = 0; // 进行滑窗过程 for (int right = 0; right < N; right++) { // A1 if (nums[right] == 0) { win_0++; } // A2 while (win_0 > K) { if (nums[left] == 0) { win_0--; } left++; } // A3 ans = max(ans, right - left + 1); } // 输出答案 cout N >> M; // 胡杨总数、未成活数目 vector trees(M); // 未成活胡杨的位置 for (int i = 0; i < M; i++) { cin >> trees; } cin >> K; // 补种数目 unordered_map treeLeft; // 构建tree_left哈希表用于表示某棵死树 treeLeft[trees[0]] = trees[0] - 1; // 第一棵死树为trees[0]，由于编号是从1开始，所以其左边一共有trees[0] - 1棵连续的活树 for (int i = 1; i < M; i++) { int tree = trees; // 当前死树 int preTree = trees[i - 1]; // 上一棵死树的编号 treeLeft[tree] = tree - preTree - 1; // 两棵树之间的连续活树的数目为 tree - pre_tree - 1 } unordered_map treeRight; // 构建tree_right哈希表用于表示某棵死树 treeRight[trees[M - 1]] = N - trees[M - 1]; // 最后一棵死树为trees[-1]，最后一棵树的编号为N，所以其右边一共有N - trees[-1]棵连续的活树 for (int i = 0; i < M - 1; i++) { int tree = trees; // 当前死树 int nxtTree = trees[i + 1]; // 下一棵死树的编号 treeRight[tree] = nxtTree - tree - 1; // 两棵树之间的连续活树的数目为 nxt_tree - tree - 1 } int winSum = K + treeLeft[trees[0]]; // 考虑第一个固定滑窗的情况，这个滑窗包含了最开始的K棵死树，如果把这些树都种下 for (int i = 0; i < K; i++) { winSum += treeRight[trees]; // 第一个固定滑窗中的连续成活胡杨的数目由以下部分构成：1. K棵补种的树 2. 第一棵死树trees[0]左边所有连续成活的树 3. 这K棵死树右边的连续成活的树 } int ans = winSum; // 初始化答案变量为第一个固定滑窗的结果 for (int right = K, left = 0; right < M; right++, left++) { int idx = trees[right]; // 对于每一个右指针right所指的元素idx，将idx右边的连续成活胡杨，加入窗口和win_sum中 winSum += treeRight[idx]; int idxLeft = trees[left]; // 对于left所指的元素idxLeft，将idxLeft左边的连续成活胡杨，从窗口和win_sum中减出 winSum -= treeLeft[idxLeft]; ans = max(ans, winSum); // 更新ans，取ans和win_sum中的较大值进行更新 } cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
