简答题
偏难
#7508
胖达与盆盆奶 大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样…
胖达与盆盆奶
大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。另一方面,因为它们是排好队的,所以每只胖达只能看到身边胖达的奶有多少,如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶,当另一份盆盆奶多出至少 100 毫升的时候,它们才能感觉到是“更多”了,否则没感觉。
现在给定一排胖达的体重,请你帮饲养员计算一下,在保持给定队形的前提下,至少应该准备多少毫升的盆盆奶?
时间限制:6000
内存限制:65535
输入
输入首先在第一行给出正整数 n(≤ 104),为胖达的个数。随后一行给出 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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++
#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;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, ans = 0;
int A[10005], L[10005] = {0}, R[10005] = {0};
// 读取胖达的个数
scanf("%d", &n);
// 读取每只胖达的体重
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
// 计算 L 数组
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;
}
}
// 计算 R 数组
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;
}
// 输出结果
printf("%d\n", ans);
return 0;
}</pre>
这道题暂未补解析。