AtCoder Beginner Contest 176 C Problem "Step" Explanation (Python3, C ++, Java)

Hello everyone! This is Rute! This article will explain the C problem </ b> of the AtCoder Beginner Contest 176 problem! !! If you have not seen the explanation of Problem A / Problem B </ b>, please check from the link shown in the table below.

Links to each problem / explanation

A B C
ABC176 A ABC176B This article! !!

Now, let's start explaining the C problem </ b>.

Problem summary

$ N $ people are lined up in a row, and the height of the $ i $ th person from the front is $ A_i $. I would like to install a stepping stone with a height of $ 0 $ or more at the feet of each person so that all people meet the following conditions.

conditions: When comparing heights (with my height) with a stepping stone, there is no person taller than me before me.

Find the minimum total height of the steps when this condition is met. Problem URL: https://atcoder.jp/contests/abc176/tasks/abc176_c

Constraint

・ $ 1 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 1 \ leq A_i \ leq 10 ^ 9 $ ・ All inputs are integers

solution

Consider the example in sample 1.

ABC176-C 解説.png

Because there is no one taller than you before you. ⇔ If there is a person taller than you, adjust your height to the taller person </ b> With that said, it seems that the height of the platform can be set to minimum </ font>.

In sample 2, everyone is at the same height, so the height of the platform is 0 and the sum is 0.

If there is a person taller than you in front of you, the condition of adjusting your height to the taller person </ b> can be rephrased as the following conditions.

In the sequence of $ A_1, A_2, ... A_N $, only the monotonously decreasing part should be adjusted to the height of the stepping stone so that it will be the same height as the previous person. </ B>

For example, in the case of a monotonically increasing sequence, there are only people higher than you </ b> behind you. This eliminates the need to adjust the height of the platform. However, there is an exception to this, as shown in Figure 2 below, when there is a tall person in front of A and the same height as the person behind A </ b> (this is monotonous). You have to adjust the height of A and the both </ b> stepping stones of the person behind it (not a reduction). ABC176-C 解説2.png

Therefore, you should perform the following processing.

processing

Define ʻans as the desired value and initialize it with $ 0 $. At (1, N-1), turn the following loop. If ʻA [i-1]> A [i], add the difference of ʻA [i-1] -A [i] to ʻans and add ʻA [i]to ʻA [i-1 ] Make it the same as the value of(make the height of the platform the same as the previous person) Output ʻans`. The amount of calculation is $ O (N) $.

Below are examples of solutions in Python3, C ++, and Java.

Sample answers for each language (Python3, C ++, Java)

Example solution in Python3

{ABC176C.py}


N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(1,N):
  if A[i-1] > A[i]:
    ans += A[i-1]-A[i]
    A[i] = A[i-1]
print(ans)
Example solution in C ++

{ABC176C.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  long long int ans = 0;
  for (int i = 1; i < n; i++){
    if (a.at(i-1) > a.at(i)){
      ans = ans + (a.at(i-1)-a.at(i));
      a.at(i) = a.at(i-1);
    }
  }
  cout << ans << endl;
  return 0;
}

The value of ʻans can exceed $ 2 × 10 ^ 9 $, so let's type ʻans to long long int. (∵ 2^{31}-1 \simeq 2×10^9)

Java answer example

{ABC176C.java}


import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++){
      int A = scan.nextInt();
      a[i] = A;
    }
    long ans = 0;
    for (int i = 1; i < n; i++){
      if (a[i-1] > a[i]){
        ans = ans + (a[i-1]-a[i]);
        a[i] = a[i-1];
      }
    }
   System.out.println(ans);
  }
}

The value of ʻans can exceed $ 2 × 10 ^ 9 $, so let's type ʻans to long. (∵ 2^{31}-1 \simeq 2×10^9)

This is the explanation of ABC 176 C problem </ b> "Step". If you have any questions after reading the article, please leave a comment! !!

Recommended Posts