PAT (Level A) Autumn 2020 7-1 Panda and PP Milk

7-1 Panda and PP Milk (20 points)

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

Subject restrictions:

Topic meaning:

Given the weight of N pandas, each panda should drink at least 200ml of milk, and those with heavier body weight drink more milk. Pandas with a difference of 100ml will notice the difference in milk volume with other pandas. Now you are required to give the minimum required by all pandas. milk volume.

Algorithm idea:

I think this is a requirement to give the same distribution of milk volume changes as body weight according to the distribution of body weight. The solution is to first set the milk volume of the first panda to the minimum, and then if the weight of the subsequent pandas is greater than it, add it. 100, equal, then it is the same as it, otherwise there will be a direct downward trend and directly assign the value to 200, but because this may cause the previous milk distribution to be inconsistent with the weight distribution, then it needs to be adjusted. There are two main adjustments. Type, the first is that the weight of the current panda is heavier than the latter, but the amount of milk is equal to it, so you need to add 100 to it (there is no possibility that it will be less than the latter, because in the initial state
, the milk volume of the panda in the front was originally more than that in the back, because the panda in the back was adjusted and added 100 to make it equal to it. In the case of the original gap, it will only be equal, and will not exceed). The second type is that the current panda weighs the same as the latter, but drinks less milk than the latter (also because the latter pandas have been adjusted, and there is no situation that the same weight of milk will drink the same, because the arrival At the current j time, j+1 must have been adjusted), then for the first time when j+1 is the peak, that is, when there is a downward trend in the current period, and it does not violate the relationship between the milk quantity of the panda on the right, adjust it. Done.
Finally, count all the milk quantities and then output them.

be careful:

  • 1. Carefully figure out the two types that need to be adjusted and the value of the equal sign. I have not had the last test point before.

Submit the result:

AC code:

#include<cstdio>

using namespace std;

/*
The main idea of ​​the title: Given the weight of N pandas, each panda should drink at least 200ml of milk, and those with heavier body weight drink more milk, and a panda with a difference of 100ml will notice that it is different from other pandas.
The milk gap now requires you to give the minimum milk required for all pandas.
Algorithm idea: I think this is a requirement to give the same distribution of milk volume and body weight according to the distribution of body weight. The solution method is to first analyze the first panda
 The amount of milk is set to the minimum, and then if the weight of the following panda is greater than it, add 100, equal, then it is the same as it, otherwise it will directly show a downward trend and directly assign the value
 is 200, but since this may cause the previous milk distribution to be inconsistent with the body weight distribution, it needs to be adjusted. There are two main adjustments.
Type, the first is that the weight of the current panda is heavier than the latter, but the amount of milk is equal to it, so you need to add 100 to it (there is no possibility that it will be less than the latter, because in the initial state
,The milk volume of the panda in front was originally more than that in the back, because the panda in the back was adjusted and added 100 to make it equal to it. In the case of the original gap, it will only be equal, and will not exceed).
The second type is that the current panda weighs the same as the latter, but drinks less milk than the latter (also because the latter pandas have been adjusted, and there is no situation that the same weight of milk will drink the same, because
 When reaching the current j, j+1 must have been adjusted), then for the first time when j+1 is the peak, that is, there is a downward trend in the current period, and it does not violate the relationship between the milk quantity of the panda on the right. Adjustment is complete.
Finally, count all the milk quantities and then output them. 
*/

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;//The initial milk volume is 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{
            // The previous milk volume is 200, and here is still a downward trend 
            // Search forward for the crest and add 100 to each milk volume
            milk[i] = 200;
            for(int j=i-1;j>=0;--j){// Every panda that needs to adjust the amount of milk 
                if(weight[j+1]<weight[j]&& milk[j+1]==milk[j]){
                    // The current panda is heavier than the latter, but the milk it drinks is the same as it needs to be adjusted 
                    milk[j] = milk[j] + 100;//Add 100 to each milk quantity 
                }else if(weight[j+1]==weight[j]&&milk[j+1]>milk[j]) {
                    // The current panda is as heavy as the latter, but drinks less milk than it and needs to be adjusted 
                    milk[j] = milk[j] + 100;//Add 100 to each milk quantity 
                }else{
                    // j+1 is the peak, you can exit directly, no need to adjust, because after adjustment, it is no longer the minimum milk quantity 
                    break; 
                }
            } 
        }
    } 
    int total = 0;
    for(int i=0;i<N;++i){
        total += milk[i];
    }
    printf("%d",total);
    return 0;
} 

Tags: C++ Algorithm

Posted by mallen on Tue, 03 May 2022 19:00:45 +0300