关于算法-数据结构:PAT甲级2020年秋季考试-71-Panda-and-PP-Milk

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

题目限度：

题目粗心：

给定 N 只熊猫的体重，每一只熊猫起码喝奶 200ml, 体重大的喝奶多，相差 100ml 熊猫就会察觉到和其余熊猫奶量的差距，当初要求你给出所有熊猫所需的最低奶量。

算法思路：

自己认为这是要求依据体重的散布，给出奶量变化趋势和体重一样的散布，求解办法就是，先对第一只熊猫的奶量设置为最小，而后前面的熊猫体重如果大于它，就加 100，相等，则和它一样，否则就间接呈现降落趋势间接赋值为 200，然而因为这样有可能会导致后面的奶量散布呈现和体重散布不统一的状况，那么就须要进行调整，次要调整两种类型，第一种就是以后熊猫体重比前面的重，然而奶量却和它相等，就须要给它加 100(不会呈现比前面少的可能，因为初始状态下
，后面的熊猫的奶量原先是比前面多的，是因为前面的熊猫进行了调整，加了 100，才会导致和它相等，在原先存在差距的状况只会相等，不会超过)。第二种类型就是以后熊猫体重和前面的一样，然而喝的奶量却比前面的少(同样是因为前面的熊猫调整过了，而且也不存在体重一样喝的奶会一样的状况，因为达到以后的 j 的时候，j+ 1 肯定调整过)，那么对于第一次呈现 j + 1 为波峰的时候，也就是当期呈现降落趋势，并且也没有违反左边的熊猫的奶量关系的时候就调整结束了。
最初统计所有奶量而后输入即可。

留神点：

• 1、认真琢磨那两个须要调整的类型和等号的取值，之前让我最初一个测试点没有过。

提交后果：

AC 代码：

#include<cstdio>

using namespace std;

/*
题目粗心：给定 N 只熊猫的体重，每一只熊猫起码喝奶 200ml, 体重大的喝奶多，相差 100ml 熊猫就会察觉到和其余熊猫
奶量的差距，当初要求你给出所有熊猫所需的最低奶量。算法思路：自己认为这是要求依据体重的散布，给出奶量变化趋势和体重一样的散布，求解办法就是，先对第一只熊猫
的奶量设置为最小，而后前面的熊猫体重如果大于它，就加 100，相等，则和它一样，否则就间接呈现降落趋势间接赋值
为 200，然而因为这样有可能会导致后面的奶量散布呈现和体重散布不统一的状况，那么就须要进行调整，次要调整两种
类型，第一种就是以后熊猫体重比前面的重，然而奶量却和它相等，就须要给它加 100(不会呈现比前面少的可能，因为初始状态下，后面的熊猫的奶量原先是比前面多的，是因为前面的熊猫进行了调整，加了 100，才会导致和它相等，在原先存在差距的状况只会相等，不会超过)。第二种类型就是以后熊猫体重和前面的一样，然而喝的奶量却比前面的少(同样是因为前面的熊猫调整过了，而且也不存在体重一样喝的奶会一样的状况，因为
达到以后的 j 的时候，j+ 1 肯定调整过)，那么对于第一次呈现 j + 1 为波峰的时候，也就是当期呈现降落趋势，并且也没有违反左边的熊猫的奶量关系的时候就调整结束了。最初统计所有奶量而后输入即可。*/

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