# PAT（甲级）2020年秋季考试 7-1 Panda and PP Milk

2020-12-06 19:23:26 乔梓鑫

## 7-1 Panda and PP Milk (20分)

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``

#### 算法思路：

，前面的熊猫的奶量原先是比后面多的，是因为后面的熊猫进行了调整，加了100，才会导致和它相等，在原先存在差距的情况只会相等，不会超过) 。第二种类型就是当前熊猫体重和后面的一样，但是喝的奶量却比后面的少(同样是因为后面的熊猫调整过了，而且也不存在体重一样喝的奶会一样的情况，因为到达当前的j的时候，j+1一定调整过)，那么对于第一次出现j+1为波峰的时候，也就是当期出现下降趋势，并且也没有违背右边的熊猫的奶量关系的时候就调整完毕了。

#### 注意点：

• 1、仔细揣摩那两个需要调整的类型和等号的取值，之前让我最后一个测试点没有过。

#### AC代码：

``````#include<cstdio>

using namespace std;

/*

，前面的熊猫的奶量原先是比后面多的，是因为后面的熊猫进行了调整，加了100，才会导致和它相等，在原先存在差距的情况只会相等，不会超过) 。

*/

int main(){
int N;
scanf("%d",&N);
int weight[N];
for(int i=0;i<N;++i){
scanf("%d",&weight[i]);
}
int milk[N];
milk[0] = 200;//初始奶量为200
for(int i=1;i<N;++i){
if(weight[i]>weight[i-1]){
milk[i] = milk[i-1] + 100;
}else if(weight[i]==weight[i-1]){
milk[i] = milk[i-1];
}else{
// 前面的奶量为200了，并且这里还是下降趋势
// 向前搜寻波峰，并且每一个奶量加100
milk[i] = 200;
for(int j=i-1;j>=0;--j){// 每一个需要调整奶量的熊猫
if(weight[j+1]<weight[j]&& milk[j+1]==milk[j]){
// 当前熊猫比后面的重，但是喝的奶和它一样，需要调整
milk[j] = milk[j] + 100;//每一个奶量加100
}else if(weight[j+1]==weight[j]&&milk[j+1]>milk[j]) {
// 当前的熊猫和后面的一样重，但是喝的奶比它少，需要调整
milk[j] = milk[j] + 100;//每一个奶量加100
}else{
// j+1为波峰，直接退出即可，无需再调整，因为调整后就不在是最低奶量了
break;
}
}
}
}
int total = 0;
for(int i=0;i<N;++i){
total += milk[i];
}
printf("%d",total);
return 0;
} ``````

https://segmentfault.com/a/1190000038393041