AtCoder Beginner Contest 176 Explication de l '«étape» du problème C (Python3, C ++, Java)

Bonjour à tous! C'est Rute! Cet article est une explication du problème C </ b> du problème AtCoder Beginner Contest 176! !! Si vous n'avez pas vu l'explication de Un problème / B problème </ b>, veuillez vérifier à partir du lien indiqué dans le tableau ci-dessous.

Liens vers chaque problème / explication

A B C
ABC176 A ABC176B Cet article! !!

Maintenant, commençons à expliquer le problème C </ b>.

Résumé du problème

Les personnes de $ N $ sont alignées sur une ligne et la hauteur de la $ i $ ème personne de face est de $ A_i $. Je voudrais installer un tremplin d'une hauteur de 0 $ ou plus aux pieds de chaque personne afin que toutes les personnes remplissent les conditions suivantes.

conditions: Lorsque l'on compare les hauteurs (avec ma propre taille) à un tremplin, personne n'est plus grand que moi avant moi.

Trouvez la hauteur totale minimale des marches lorsque cette condition est remplie. URL du problème: https://atcoder.jp/contests/abc176/tasks/abc176_c

Contrainte

・ $ 1 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 1 \ leq A_i \ leq 10 ^ 9 $ ・ Toutes les entrées sont des entiers

Solution

Prenons l'exemple de l'exemple 1.

ABC176-C 解説.png

Parce qu'il n'y a personne de plus grand que moi avant moi. ⇔ S'il y a une personne plus grande que vous, ajustez votre taille à la personne la plus grande </ b> Cela dit, il semble que la hauteur de la plate-forme puisse être réglée sur minimum </ font>.

Dans l'exemple 2, tout le monde est à la même hauteur, donc la hauteur de la plate-forme est 0 et la somme est 0.

S'il y a une personne plus grande que vous devant vous, la condition d'ajuster votre taille à la personne la plus grande </ b> peut être reformulée comme les conditions suivantes.

De la séquence de $ A_1, A_2, ... A_N $, seule la partie décroissante de façon monotone doit être ajustée à la même hauteur que la personne précédente. </ B>

Par exemple, dans le cas d'un nombre de colonnes en augmentation monotone, il n'y a que des personnes plus hautes que vous </ b> derrière vous. Cela élimine le besoin d'ajuster la hauteur de la plate-forme. Cependant, il existe une exception à cela, comme le montre la figure 2 ci-dessous, lorsqu'il y a une personne de grande taille devant A et de la même hauteur que la personne derrière A </ b> (c'est monotone). Vous devez ajuster la hauteur de A et les deux </ b> pas de la personne derrière (pas de réduction). ABC176-C 解説2.png

Par conséquent, vous devez effectuer le traitement suivant.

En traitement

Définissez ʻanscomme valeur souhaitée et initialisez-la avec $ 0 $. En (1, N-1), tournez la boucle suivante. Si ʻA [i-1]> A [i], ajoutez la différence de ʻA [i-1] -A [i] à ʻans et ajoutez ʻA [i] à ʻA [i-1 ] Faites-en la même chose que la valeur de (faites en sorte que la hauteur de la plate-forme soit la même que celle de la personne précédente) Sortie ʻans`. Le montant du calcul est de O $ (N) $.

Vous trouverez ci-dessous des exemples de réponses en Python3, C ++ et Java.

Exemples de réponses pour chaque langage (Python3, C ++, Java)

Exemple de solution en 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)
Exemple de solution en 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;
}

La valeur de ʻans peut dépasser $ 2 × 10 ^ 9 $, alors tapons ʻans à long long int. (∵ 2^{31}-1 \simeq 2×10^9)

Exemple de solution en Java

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

La valeur de ʻans peut dépasser $ 2 × 10 ^ 9 $, alors tapons ʻans à long. (∵ 2^{31}-1 \simeq 2×10^9)

C'est l'explication du problème ABC 176 C </ b> "Step". Si vous avez des questions après avoir lu l'article, laissez un commentaire! !!

Recommended Posts