Lösen mit Ruby und Python AtCoder Tenka1 Programmer Contest C Kumulative Summe

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

Tenka1 Programmer Contest C - Stones Difficulty: 946

Dieses Thema, kumulative Summe

Aus dem Problem ergibt sich, dass die endgültige Anordnung der Steine ganz weiß "........", ganz schwarz "########" oder links weiß rechts schwarz "..... # ist. Wechseln Sie zu einem von ## . Ein wenig nervig ist das Muster wie ". # .... #. #.", Das linke ". #." Ist "..." und das rechte "#. #." Der Mindestwert besteht darin, ihn in zu ändern. Nehmen Sie daher die kumulative Summe von "." Und "#" von links nach rechts, überprüfen Sie die Anzahl der Änderungen an dieser Position und ermitteln Sie den Mindestwert. 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

Es ist anomal, aber es ist eine kumulative Summe.

bw.rb

min = [a[-1][0], a[-1][1]].min

Ermitteln Sie zunächst die Anzahl der Fälle, in denen alle weiß und alle schwarz sind.

tugi.rb

  min = a[-1][0] - a[i][0] + a[i][1] if min > a[-1][0] - a[i][0] + a[i][1]

Überprüfen Sie als nächstes die Nummer, wenn Sie an jeder Position zu links weiß rechts schwarz wechseln.

ord.rb

dot = '.'.ord

  if s[i] == dot

Es scheint, dass es etwas schneller ist, nach Zeichenwert zu vergleichen. 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()

Zusammenfassung

• Tenka1 C gelöst
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut