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

增高垫 网传最大号的增高垫有 16 厘米,可以一下把 1.64 米的男孩变成一米八的大汉,不少对自己身高缺乏自信的男生女生会悄悄买来穿,特别是大家站成一排拍照的…

增高垫

网传最大号的增高垫有 16 厘米,可以一下把 1.64 米的男孩变成一米八的大汉,不少对自己身高缺乏自信的男生女生会悄悄买来穿,特别是大家站成一排拍照的时候。

假设准备拍照的一排人中,只要有人看到身边紧挨着的人比自己高,就会忍不住穿增高垫,并且一定要比人家多穿一层。你的任务就是在看过这一排人的身高后,算出谁穿了最多层的增高垫。

时间限制:1000

内存限制:65536

输入

输入首先在第一行给出正整数 n(≤ 104),为一排人的个数。随后一行给出 n 个正整数,表示 n 个人的身高(厘米)。每个数值是不超过 300 的正整数,数字间以空格分隔。

输出

在一行中输出穿了最多层增高垫的人的位置和穿的层数(位序从左到右,从 1 开始)。如果有并列,按从左到右的顺序,每个人的信息占一行。


样例输入

10
150 160 186 200 170 175 180 186 186 183

样例输出

1 3
5 3
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int main() { int n; cin &gt;&gt; n; vector&lt;int&gt; height(n); for (int i = 0; i &lt; n; ++i) { cin &gt;&gt; height[i]; } vector&lt;int&gt; layers(n, 0); // 从左到右处理左边比自己高的情况 for (int i = 1; i &lt; n; ++i) { if (height[i - 1] &gt; height[i]) { layers[i] = layers[i - 1] + 1; } } // 从右到左处理右边比自己高的情况 for (int i = n - 2; i &gt;= 0; --i) { if (height[i + 1] &gt; height[i]) { layers[i] = max(layers[i], layers[i + 1] + 1); } } // 找出最大层数 int max_layer = *max_element(layers.begin(), layers.end()); // 输出所有层数等于最大层数的位置 for (int i = 0; i &lt; n; ++i) { if (layers[i] == max_layer) { cout &lt;&lt; i + 1 &lt;&lt; " " &lt;&lt; max_layer &lt;&lt; endl; } } return 0; }</pre>
这道题暂未补解析。