AtCoder Regular Contets C - Attention Difficulty: 641
Dieses Thema, kumulative Summe Ruby Unter Berücksichtigung von "WEWEWEEEWWWE" in Eingabebeispiel 2 wird es zu "WEWEWEEiWWWE", und die Gesamtzahl der "W" auf der linken Seite von "i" und die Anzahl der "E" auf der rechten Seite ist die erforderliche Anzahl von Personen. Von der linken "0" zur rechten "n-1" der Zeichenkette nimmt "E" monoton ab und "W" monoton zu, so dass die ** kumulative Summe ** als Methode zur Reduzierung des Berechnungsaufwands verwendet wird. ..
ruby.rb
n = gets.to_i
s = gets.chomp
e = (s[0] == 'E' ? [1] : [0])
w = (s[0] == 'W' ? [1] : [0])
1.upto(n - 1) do |i|
if (s[i] == 'E')
e[i] = e[i - 1] + 1
w[i] = w[i - 1]
else
e[i] = e[i - 1]
w[i] = w[i - 1] + 1
end
end
w.unshift(0)
min = Float::INFINITY
0.upto(n - 1) do |i|
min = e[-1] - e[i] + w[i] if min > e[-1] - e[i] + w[i]
end
puts min
sum.rb
1.upto(n - 1) do |i|
if (s[i] == 'E')
e[i] = e[i - 1] + 1
w[i] = w[i - 1]
else
e[i] = e[i - 1]
w[i] = w[i - 1] + 1
end
end
Die kumulative Summe wird hier berechnet.
inf.rb
min = Float::INFINITY
Infinity wird mit Float :: INFINITY
gesetzt.
Python
python.py
import sys
n = int(input())
s = input()
e = [0] * n
w = [0] * (n + 1)
e[0] = 1 if s[0] == 'E' else 0
w[0] = 0
w[1] = 1 if s[0] == 'W' else 0
for i in range(1, n):
if s[i] == 'E':
e[i] = e[i - 1] + 1
w[i + 1] = w[i]
else:
e[i] = e[i - 1]
w[i + 1] = w[i] + 1
min = sys.maxsize
for i in range(n):
if min > e[-1] - e[i] + w[i]:
min = e[-1] - e[i] + w[i]
print(min)
max.py
min = sys.maxsize
Die Obergrenze für Ganzzahlen wird in sys.maxsize
festgelegt.
Perl
perl.pl
chomp (my $n = <STDIN>);
chomp (my $s = <STDIN>);
my (@e, @w);
$e[0] = (substr($s, 0, 1) eq 'E' ? 1 : 0);
$w[0] = (substr($s, 0, 1) eq 'W' ? 1 : 0);
for my $i (1..$n-1) {
if (substr($s, $i, 1) eq 'E') {
$e[$i] = $e[$i - 1] + 1;
$w[$i] = $w[$i - 1];
} else {
$e[$i] = $e[$i - 1];
$w[$i] = $w[$i - 1] + 1;
}
}
unshift @w, 0;
my $min = inf;
for my $i (0..$n-1) {
$min = $e[-1] - $e[$i] + $w[$i] if $min > $e[-1] - $e[$i] + $w[$i];
}
print "$min\n";
inf.pl
my $min = inf;
Unendlichkeit wird mit "inf" gesetzt. Java
java.java
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
char s[] = sc.next().toCharArray();
sc.close();
int e[] = new int[n];
int w[] = new int[n + 1];
w[0] = 0;
if (s[0] == 'E') {
e[0] = 1;
w[1] = 0;
} else {
e[0] = 0;
w[1] = 1;
}
for (int i = 1; i < n; i++) {
if (s[i] == 'E') {
e[i] = e[i - 1] + 1;
w[i + 1] = w[i];
} else {
e[i] = e[i - 1];
w[i + 1] = w[i] + 1;
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (min > e[n - 1] - e[i] + w[i])
min = e[n - 1] - e[i] + w[i];
}
System.out.println(min);
}
}
inf.java
int min = Integer.MAX_VALUE;
Der Maximalwert der Ganzzahl wird in "Integer.MAX_VALUE" festgelegt.
Ruby | Python | Perl | Java | |
---|---|---|---|---|
Codelänge | 379 Byte | 433 Byte | 488 Byte | 962 Byte |
Ausführungszeit | 160 ms | 302 ms | 255 ms | 181 ms |
Erinnerung | 7808 KB | 17552 KB | 22604 KB | 32136 KB |
Referenzierte Site