首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13192

园林修整 园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修…

园林修整

园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比,所以需要你替他想一种最省力的修整方案。

时间限制: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 的树。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>参考代码:<br/></p><pre class="brush:cpp;toolbar:false">#include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;set&gt; using namespace std; struct Result {     int changes;     int replaces;     vector&lt;int&gt; removed; }; Result processDirection(const vector&lt;int&gt;&amp; a, bool nonDecreasing) {     int n = a.size();     vector&lt;int&gt; dp(n, 1);     vector&lt;int&gt; prev(n, -1);     for (int i = 0; i &lt; n; ++i) {         for (int j = 0; j &lt; i; ++j) {             bool valid = nonDecreasing ? (a[j] &lt;= a[i]) : (a[j] &gt;= a[i]);             if (valid &amp;&amp; dp[j] + 1 &gt; dp[i]) {                 dp[i] = dp[j] + 1;                 prev[i] = j;             }         }     }     int maxLen = *max_element(dp.begin(), dp.end());     vector&lt;int&gt; candidates;     for (int i = 0; i &lt; n; ++i) {         if (dp[i] == maxLen) {             candidates.push_back(i);         }     }     int bestReplace = 1e9;     vector&lt;int&gt; bestIndices;     for (int candidate : candidates) {         vector&lt;int&gt; path;         int current = candidate;         while (current != -1) {             path.push_back(current);             current = prev[current];         }         reverse(path.begin(), path.end());         set&lt;int&gt; pathSet(path.begin(), path.end());         vector&lt;int&gt; sortedPath(path.begin(), path.end());         sort(sortedPath.begin(), sortedPath.end());         int replace = 0;         for (int k = 0; k &lt; n; ++k) {             if (pathSet.count(k)) continue;             auto it = upper_bound(sortedPath.begin(), sortedPath.end(), k);             if (it != sortedPath.begin()) {                 int leftIdx = *(--it);                 if (a[k] &lt; a[leftIdx]) {                     replace++;                 }             }         }         if (replace &lt; bestReplace || (replace == bestReplace &amp;&amp; path.size() &gt; bestIndices.size())) {             bestReplace = replace;             bestIndices = sortedPath;         }     }     set&lt;int&gt; reserved(bestIndices.begin(), bestIndices.end());     vector&lt;int&gt; removed;     for (int i = 0; i &lt; n; ++i) {         if (!reserved.count(i)) {             removed.push_back(i + 1);         }     }     sort(removed.begin(), removed.end());     return { n - maxLen, bestReplace, removed }; } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     int N;     cin &gt;&gt; N;     vector&lt;int&gt; a(N);     for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; a[i];     }     bool isNonDescending = true;     for (int i = 1; i &lt; N; ++i) {         if (a[i] &lt; a[i-1]) {             isNonDescending = false;             break;         }     }     if (isNonDescending) {         cout &lt;&lt; "Non-descending\n";         return 0;     }     bool isNonAscending = true;     for (int i = 1; i &lt; N; ++i) {         if (a[i] &gt; a[i-1]) {             isNonAscending = false;             break;         }     }     if (isNonAscending) {         cout &lt;&lt; "Non-ascending\n";         return 0;     }     Result asc = processDirection(a, true);     Result desc = processDirection(a, false);     bool useAsc;     if (asc.changes &lt; desc.changes) {         useAsc = true;     } else if (asc.changes &gt; desc.changes) {         useAsc = false;     } else {         useAsc = (asc.replaces &lt;= desc.replaces);     }     Result res = useAsc ? asc : desc;     cout &lt;&lt; res.changes &lt;&lt; '\n';     for (size_t i = 0; i &lt; res.removed.size(); ++i) {         if (i &gt; 0) cout &lt;&lt; ' ';         cout &lt;&lt; res.removed[i];     }     cout &lt;&lt; '\n';     return 0; }</pre>
这道题暂未补解析。