简答题
偏难
#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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> height(n);
for (int i = 0; i < n; ++i) {
cin >> height[i];
}
vector<int> layers(n, 0);
// 从左到右处理左边比自己高的情况
for (int i = 1; i < n; ++i) {
if (height[i - 1] > height[i]) {
layers[i] = layers[i - 1] + 1;
}
}
// 从右到左处理右边比自己高的情况
for (int i = n - 2; i >= 0; --i) {
if (height[i + 1] > 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 < n; ++i) {
if (layers[i] == max_layer) {
cout << i + 1 << " " << max_layer << endl;
}
}
return 0;
}</pre>
这道题暂未补解析。