1172 Panda and PP Milk – PAT甲级真题

PP milk （盆盆奶）is Pandas’ favorite. They would line up to enjoy it as show in the picture. On the other hand, they could drink in peace only if they believe that the amount of PP milk is fairly distributed, that is, fatter panda can have more milk, and the ones with equal weight may have the same amount. Since they are lined up, each panda can only compare with its neighbor(s), and if it thinks this is unfair, the panda would fight with its neighbor.

Given that the minimum amount of milk a panda must drink is 200 ml. It is only when another bowl of milk is at least 100 ml more than its own that a panda can sense the difference.

Now given the weights of a line of pandas, your job is to help the breeder（饲养员）to decide the minimum total amount of milk that he/she must prepare, provided that the pandas are lined up in the given order.

Input Specification:

Each input file contains one test case. For each case, first a positive integer n (≤10^4) is given as the number of pandas. Then in the next line, n positive integers are given as the weights (in kg) of the pandas, each no more than 200. the numbers are separated by spaces.

Output Specification:

For each test case, print in a line the minimum total amount of milk that the breeder must prepare, to make sure that all the pandas can drink in peace.

Sample Input:

10
180 160 100 150 145 142 138 138 138 140

Sample Output:

3000

Hint:

The distribution of milk is the following:

400 300 200 500 400 300 200 200 200 300

题目大意：大熊猫，俗称“胖达”，会排队吃盆盆奶。它们能和谐吃奶的前提，是它们认为盆盆奶的分配是“公平”的，即：更胖的胖达能吃到更多的奶，等胖的胖达得吃到一样多的奶。另一方面，因为它们是排好队的，所以每只胖达只能看到身边胖达的奶有多少，如果觉得不公平就会抢旁边小伙伴的奶吃。已知一只胖达每次最少要吃 200 毫升的奶，当另一份盆盆奶多出至少 100 毫升的时候，它们才能感觉到是“更多”了，否则没感觉。现在给定一排胖达的体重，请你帮饲养员计算一下，在保持给定队形的前提下，至少应该准备多少毫升的盆盆奶。

分析：使用数组A记录每个熊猫的体重，L[i]表示第i个数的右边有几个连续下降的数（过程中可以有相等的数字，但是只记录不重复的数字的数量），R[i]则表示第i个数左边有几个连续下降的数（也是可以相等但是不记录）。从左到右遍历每一个i，然后看一下它右边有多少个连续下降的数。从右到左同理，看一下i的左边有多少个连续下降的数。对于每一只熊猫，取L[i]和R[i]中较大的那个数*100+200，就是这只熊猫应该喝的牛奶的毫升数。最后计算他们的总和就可以啦。

#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;
}

#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 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版