题解
2023-12-03 10:47:00
发布于：广东
12阅读
0回复
0点赞
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：
①每个孩子至少分配到 1 个糖果。
②评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
输入格式
两行整数。
第一行一个整数 N(1≤N≤1e4)，表示孩子数。
第二行 N 个正整数 (≤1e9)，表示对应孩子的评分。
输出格式
一个整数，表示至少需要准备的糖果数。
样例组
输入#1
6
1 3 5 4 3 3
输出#1
10
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int n, ans;
int s[10005], l[10005], r[10005];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
l[i] = r[i] = 1;
}
for (int i = 2; i <= n; i++) {
if (s[i] > s[i - 1]) {
l[i] = l[i - 1] + 1;
}
}
for (int i = n - 1; i >= 1; i--) {
if (s[i] > s[i + 1]) {
r[i] = r[i + 1] + 1;
}
}
for (int i = 1; i <= n; i++) {
ans += max(l[i], r[i]);
}
printf("%d\n", ans);
return 0;
}
有帮助，赞一个