首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; using namespace std; int n, ans, A[10005], L[10005], R[10005]; int main(){     cin &gt;&gt; n;     for (int i = 1; i &lt;= n; i++) cin &gt;&gt; A[i];     for (int i = 1; i &lt; n; i++) {         int j = i;         while(j + 1 &lt;= n &amp;&amp; A[j] &gt;= A[j + 1]) {             if (A[j] &gt; A[j + 1]) ++L[i];             ++j;         }     }     for (int i = n; i &gt; 1; i--) {         int j = i;         while(j - 1 &gt;= 1 &amp;&amp; A[j] &gt;= A[j - 1]) {             if (A[j] &gt; A[j - 1]) ++R[i];             --j;         }     }     for (int i = 1; i &lt;= n; i++) ans += max(L[i], R[i]) * 100 + 200;     cout &lt;&lt; ans;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; int max(int a, int b) {     return a &gt; b ? a : b; } int main() {     int n, ans = 0;     int A[10005], L[10005] = {0}, R[10005] = {0};     // 读取胖达的个数     scanf("%d", &amp;n);     // 读取每只胖达的体重     for (int i = 1; i &lt;= n; i++) {         scanf("%d", &amp;A[i]);     }     // 计算 L 数组     for (int i = 1; i &lt; n; i++) {         int j = i;         while (j + 1 &lt;= n &amp;&amp; A[j] &gt;= A[j + 1]) {             if (A[j] &gt; A[j + 1]) ++L[i];             ++j;         }     }     // 计算 R 数组     for (int i = n; i &gt; 1; i--) {         int j = i;         while (j - 1 &gt;= 1 &amp;&amp; A[j] &gt;= A[j - 1]) {             if (A[j] &gt; A[j - 1]) ++R[i];             --j;         }     }     // 计算总量     for (int i = 1; i &lt;= n; i++) {         ans += max(L[i], R[i]) * 100 + 200;     }     // 输出结果     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。