大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。另一方面,因为它们是排好队的,所以每只胖达只能看到身边胖达的奶有多少,如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶,当另一份盆盆奶多出至少 100 毫升的时候,它们才能感觉到是“更多”了,否则没感觉。
现在给定一排胖达的体重,请你帮饲养员计算一下,在保持给定队形的前提下,至少应该准备多少毫升的盆盆奶?
输入格式:
输入首先在第一行给出正整数 n(≤10^4),为胖达的个数。随后一行给出 n 个正整数,表示 n 只胖达的体重(公斤)。每个数值是不超过 200 的正整数,数字间以空格分隔。
输出格式:
在一行中输出至少应该准备多少毫升的盆盆奶。
输入样例:
10
180 160 100 150 145 142 138 138 138 140
输出样例:
3000
样例解释:
盆盆奶的分配量顺序为:
400 300 200 500 400 300 200 200 200 300
分析:使用数组A记录每个熊猫的体重,L[i]表示第i个数的右边有几个连续下降的数(过程中可以有相等的数字,但是只记录不重复的数字的数量),R[i]则表示第i个数左边有几个连续下降的数(也是可以相等但是不记录)。从左到右遍历每一个i,然后看一下它右边有多少个连续下降的数。从右到左同理,看一下i的左边有多少个连续下降的数。对于每一只熊猫,取L[i]和R[i]中较大的那个数*100+200,就是这只熊猫应该喝的牛奶的毫升数。最后计算他们的总和就可以啦。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; int n, ans, A[10005], L[10005], R[10005]; int main(){ cin >> n; for (int i = 1; i <= n; i++) cin >> A[i]; for (int i = 1; i < n; i++) { int j = i; while(j + 1 <= n && A[j] >= A[j + 1]) { if (A[j] > A[j + 1]) ++L[i]; ++j; } } for (int i = n; i > 1; i--) { int j = i; while(j - 1 >= 1 && A[j] >= A[j - 1]) { if (A[j] > A[j - 1]) ++R[i]; --j; } } for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200; cout << ans; return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼