Tenka1 Programmer Contest C - Stones Difficulty: 946
Ce thème, somme cumulée
D'après le problème, la disposition finale des pierres est toute blanche ........, toute noire ########, ou gauche blanche droite noire..... # Passez à l'un des ##.
Un peu ennuyeux est un modèle comme . # .... #. # ., La gauche. # . Est ... et la droite #. # . Est#### La valeur minimale est de le changer en.
Par conséquent, prenez la somme cumulée de . et # de gauche à droite, vérifiez le nombre de changements à cette position et trouvez la valeur minimale.
Ruby
ruby.rb
n = gets.to_i
s = gets.chomp.bytes
dot = '.'.ord
a = Array.new(n){Array.new(2, 0)}
if s[0] == dot
a[0][0] = 1
else
a[0][1] = 1
end
1.upto(n - 1) do |i|
if s[i] == dot
a[i][0] = a[i - 1][0] + 1
a[i][1] = a[i - 1][1]
else
a[i][0] = a[i - 1][0]
a[i][1] = a[i - 1][1] + 1
end
end
min = [a[-1][0], a[-1][1]].min
n.times do |i|
min = a[-1][0] - a[i][0] + a[i][1] if min > a[-1][0] - a[i][0] + a[i][1]
end
puts min
rui.rb
1.upto(n - 1) do |i|
if s[i] == dot
a[i][0] = a[i - 1][0] + 1
a[i][1] = a[i - 1][1]
else
a[i][0] = a[i - 1][0]
a[i][1] = a[i - 1][1] + 1
end
end
C'est anormal, mais c'est une somme cumulative.
bw.rb
min = [a[-1][0], a[-1][1]].min
Tout d'abord, déterminez le nombre de cas lorsque tous sont blancs et quand tous sont noirs.
tugi.rb
min = a[-1][0] - a[i][0] + a[i][1] if min > a[-1][0] - a[i][0] + a[i][1]
Ensuite, vérifiez le nombre lors du passage à gauche blanc droit noir à chaque position.
ord.rb
dot = '.'.ord
if s[i] == dot
Il semble que la comparaison par valeur de caractère soit un peu plus rapide. Python
python.py
from sys import stdin
def main():
input = stdin.readline
n = int(input())
s = input()
a = [[0, 0] for _ in range(n)]
if s[0] == '.':
a[0][0] = 1
else:
a[0][1] = 1
for i in range(1, n):
if s[i] == '.':
a[i][0] = a[i - 1][0] + 1
a[i][1] = a[i - 1][1]
else:
a[i][0] = a[i - 1][0]
a[i][1] = a[i - 1][1] + 1
min = a[-1][0] if a[-1][0] < a[-1][1] else a[-1][1]
for i in range(n):
if min > a[-1][0] - a[i][0] + a[i][1]:
min = a[-1][0] - a[i][0] + a[i][1]
print(min)
main()
| Ruby | Python | |
|---|---|---|
| Longueur du code(Byte) | 457 | 631 |
| Temps d'exécution(ms) | 175 | 186 |
| Mémoire(KB) | 16208 | 30024 |
Recommended Posts