刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
3.园林修整
园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了，就需要裁剪；如果太矮了，则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比，所以需要你替他想一种最省力的修整方案。
时间限制：10000
内存限制：65536
输入
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000)，随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内，同行数字间以空格分隔。
输出
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号（从 1 开始）。如果解不唯一，输出那个需要最少替换树木的解，题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔，行首尾不得有多余空格。 如果没有树需要调整，则根据树高的升降性质，在一行中输出 Non-ascending（表示“非递增”）或 Non-descending（表示非递减）。
样例输入
样例1：
10
2 3 8 2 4 5 10 1 7 11
样例2：
3
1 2 3
样例输出
样例1：
4
2 3 7 8
样例2：
Non-descending
提示
样例1解释： 首先，要将树木修整成按高度非递减的样式，我们需要调整 4 棵树；而要修整成非递增样式，则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次，存在 4 种不同的递增序列解：
1、保持树高为 2、3、4、5、10、11 的树不变，我们需要替换掉高度为 2、1、7 的 3 棵树，因为它们太矮了；
2、保持树高为 2、3、4、5、7、11 的树不变，我们需要替换掉高度为 2、1 的 2 棵树；
3、保持树高为 2、2、4、5、10、11 的树不变，我们需要替换掉高度为 1、7 的 2 棵树；
4、保持树高为 2、2、4、5、7、11 的树不变，我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解，即裁剪编号为 2、3、7（对应高度为 3、8、10）的树，替换掉第 8 棵高度为 1 的树。
园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了，就需要裁剪；如果太矮了，则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比，所以需要你替他想一种最省力的修整方案。
时间限制：10000
内存限制：65536
输入
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000)，随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内，同行数字间以空格分隔。
输出
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号（从 1 开始）。如果解不唯一，输出那个需要最少替换树木的解，题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔，行首尾不得有多余空格。 如果没有树需要调整，则根据树高的升降性质，在一行中输出 Non-ascending（表示“非递增”）或 Non-descending（表示非递减）。
样例输入
样例1：
10
2 3 8 2 4 5 10 1 7 11
样例2：
3
1 2 3
样例输出
样例1：
4
2 3 7 8
样例2：
Non-descending
提示
样例1解释： 首先，要将树木修整成按高度非递减的样式，我们需要调整 4 棵树；而要修整成非递增样式，则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次，存在 4 种不同的递增序列解：
1、保持树高为 2、3、4、5、10、11 的树不变，我们需要替换掉高度为 2、1、7 的 3 棵树，因为它们太矮了；
2、保持树高为 2、3、4、5、7、11 的树不变，我们需要替换掉高度为 2、1 的 2 棵树；
3、保持树高为 2、2、4、5、10、11 的树不变，我们需要替换掉高度为 1、7 的 2 棵树；
4、保持树高为 2、2、4、5、7、11 的树不变，我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解，即裁剪编号为 2、3、7（对应高度为 3、8、10）的树，替换掉第 8 棵高度为 1 的树。
使用微信搜索喵呜刷题，轻松应对考试！
答案：
解析：
首先读取输入，获取树的数量和每个树的高度。对树的高度进行排序，然后遍历排序后的数组。在遍历过程中，我们维护一个变量来记录当前位置的树是否需要裁剪或替换。如果当前树的高度大于前一个树的高度，并且需要裁剪或替换操作，则累加操作次数，并记录需要裁剪或替换的树的编号。如果遍历完整个数组后，没有树需要调整，则输出Non-ascending或Non-descending表示树的高度是非递增或非递减的。否则，输出裁剪次数和需要裁剪的树的编号。为了得到最优解，我们需要按照题目要求的规则选择裁剪还是替换操作，即优先选择裁剪操作。在实现过程中，我们可以使用一个布尔数组来记录每个树是否需要裁剪或替换，然后遍历整个数组并记录需要操作的树的编号。最后输出操作次数和需要操作的树的编号即可。
时间复杂度为O(nlogn)，其中n为树的数量。因为我们需要对树的高度进行排序，排序的时间复杂度为O(nlogn)。然后我们需要遍历整个排序后的数组一次，时间复杂度为O(n)。因此总的时间复杂度为O(nlogn)。
创作类型：
原创
本文链接：3.园林修整园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
