AtCoder Anfängerwettbewerb 176 C Problem "Schritt" Erklärung (Python3, C ++, Java)
Hallo zusammen! Das ist Rute! Dieser Artikel ist eine Erklärung des C-Problems </ b> des AtCoder Beginner Contest 176-Problems! !! Wenn Sie die Erklärung von A Problem / B Problem </ b> nicht gesehen haben, überprüfen Sie dies bitte über den in der folgenden Tabelle gezeigten Link.
Links zu jedem Problem / jeder Erklärung
| A | B | C |
|---|---|---|
| ABC176 A | ABC176B | Dieser Beitrag! !! |
Beginnen wir nun mit der Erläuterung des C-Problems </ b>.
Problemzusammenfassung
$ N $ Personen sind in einer Reihe aufgereiht, und die Größe der $ i $ -ten Person von vorne beträgt $ A_i $. Ich möchte ein Sprungbrett mit einer Höhe von $ 0 $ oder mehr zu Füßen jeder Person installieren, damit alle Menschen die folgenden Bedingungen erfüllen.
Bedingungen: Wenn ich Höhen (mit meiner eigenen Größe) mit einem Sprungbrett vergleiche, gibt es keine Person, die größer ist als ich vor mir.
Ermitteln Sie die minimale Gesamthöhe der Stufen, wenn diese Bedingung erfüllt ist. Problem-URL: https://atcoder.jp/contests/abc176/tasks/abc176_c
Zwang
・ $ 1 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 1 \ leq A_i \ leq 10 ^ 9 $ ・ Alle Eingänge sind ganze Zahlen
Lösung
Betrachten Sie das Beispiel in Beispiel 1.
Weil vor mir niemand größer ist als ich. ⇔ Wenn eine Person größer als Sie ist, passen Sie Ihre Größe an die größere Person </ b> an Vor diesem Hintergrund scheint die Höhe der Plattform auf Minimum </ font> eingestellt werden zu können.
In Beispiel 2 befinden sich alle auf derselben Höhe, sodass die Höhe der Plattform 0 und die Summe 0 beträgt.
Wenn sich eine Person vor Ihnen befindet, die größer als Sie ist, kann die Bedingung zum Anpassen Ihrer Körpergröße an die größere Person </ b> wie folgt umformuliert werden.
Von der Folge von $ A_1, A_2, ... A_N $ sollte nur der monoton abnehmende Teil auf die gleiche Höhe wie die vorherige Person eingestellt werden. </ B>
Zum Beispiel gibt es bei einer monoton ansteigenden Anzahl von Spalten nur Personen hinter Ihnen </ b>.
Dadurch muss die Höhe der Plattform nicht mehr angepasst werden.
Es gibt jedoch eine Ausnahme, wie in Abbildung 2 unten gezeigt, wenn sich vor A eine große Person befindet und dieselbe Größe wie die Person hinter A </ b> hat (dies ist eintönig). Sie müssen die Höhe von A und die beide </ b> Schritte der Person dahinter anpassen (keine Reduzierung).
Daher sollten Sie die folgende Verarbeitung durchführen.
wird bearbeitet
Definieren Sie ans als gewünschten Wert und initialisieren Sie ihn mit $ 0 $.
Drehen Sie bei (1, N-1) die folgende Schleife.
Wenn "A [i-1]> A [i]", addiere die Differenz von "A [i-1] -A [i]" zu "ans" und addiere "A [i]" zu "A [i-1" ] Machen Sie es gleich dem Wert von (machen Sie die Höhe der Plattform gleich wie die vorherige Person) Ausgabe ans`.
Der Berechnungsbetrag beträgt $ O (N) $.
Nachfolgend finden Sie Beispiele für Antworten in Python3, C ++ und Java.
Beispielantworten für jede Sprache (Python3, C ++, Java)
Beispiellösung 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)
{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)
Lösungsbeispiel 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;
}
Der Wert von "ans" kann $ 2 × 10 ^ 9 $ überschreiten. Geben Sie also "ans" in "long long int" ein.
(∵ 2^{31}-1 \simeq 2×10^9 )
{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;
}
Der Wert von "ans" kann $ 2 × 10 ^ 9 $ überschreiten. Geben Sie also "ans" in "long long int" ein.
(∵
Java-Antwortbeispiel
{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);
}
}
Der Wert von "ans" kann $ 2 × 10 ^ 9 $ überschreiten. Geben Sie also "ans" in "long" ein.
(∵ 2^{31}-1 \simeq 2×10^9 )
{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);
}
}
Der Wert von "ans" kann $ 2 × 10 ^ 9 $ überschreiten. Geben Sie also "ans" in "long" ein.
(∵
Dies ist die Erklärung des ABC 176 C-Problems </ b> "Schritt". Wenn Sie nach dem Lesen des Artikels Fragen haben, hinterlassen Sie bitte einen Kommentar! !!