Einführung

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

Dieses Thema

AtCoder CODE FESTIVAL 2016 qual C B - K Kuchen * Difficulty: 905

Dieses Thema, Prioritätswarteschlange

Es handelt sich um ein Problem wie eine erweiterte Version von * AtCoder ABC141 D mit Ruby, Python und Java lösen *, das zuvor behoben wurde.

Nimmt das Maximum und das zweite Maximum eines bestimmten Arrays aus der Warteschlange, subtrahiert 1 und stellt es wieder in die Warteschlange. Wiederholen Sie diesen Vorgang und verlassen Sie die Schleife, wenn die Warteschlange kleiner als eins ist.

Es gibt auch eine mathematische Lösung.

Ruby mathematische Lösung

`ruby.rb`


k = gets.to_i
a = gets.split.map(&:to_i).max
puts [0, 2 * a - k - 1].max

Ich werde auf den Maximalwert achten und ihn lösen, aber das erfrischende Gefühl ist erstaunlich. Ruby Heap

`ruby.rb`


class Heap
  attr_reader :size
  def initialize(up: false)
    @up = up
    @heap = []
    @size = 0
  end
  def sum
    x = 0
    @size.times do |i|
      x += @heap[i]
    end
    x
  end
  def push(n)
    n = -n if @up
    i = @size
    while i > 0
      pid = (i - 1) / 2
      break if n >= @heap[pid]
      @heap[i] = @heap[pid]
      i = pid
    end
    @heap[i] = n
    @size += 1
  end
  def pop
    return nil if @size == 0
    top = @heap[0]
    @size -= 1
    n = @heap[@size]
    i = 0
    while i * 2 + 1 < @size
      cid1 = i * 2 + 1
      cid2 = cid1 + 1
      if cid2 < @size && @heap[cid2] < @heap[cid1]
        cid1 = cid2
      end
      break if @heap[cid1] >= n
      @heap[i] = @heap[cid1]
      i = cid1
    end
    @heap[i] = n
    if @up
      -top
    else
      top
    end
  end
end

gets
a = gets.split.map(&:to_i)
h = Heap.new(up: true)
a.each do |x|
  h.push(x)
end
while h.size > 1
  u = h.pop
  v = h.pop
  h.push(u - 1) if u - 1 > 0
  h.push(v - 1) if v - 1 > 0
end
if h.size == 0
  puts "0"
else
  puts h.pop - 1
end

`up.rb`


  def initialize(up: false)
    @up = up

Letztes Mal * Die Klasse wurde verbessert, sodass der Maximalwert und der Minimalwert mit einem Flag umgeschaltet werden können.

`heap.rb`


while h.size > 1
  u = h.pop
  v = h.pop
  h.push(u - 1) if u - 1 > 0
  h.push(v - 1) if v - 1 > 0
end

Nehmen Sie zwei, subtrahieren Sie sie und stellen Sie sie wieder in die Warteschlange, wenn sie 1 oder mehr sind.

Python mathematische Lösung

`python.py`


from sys import stdin

def main():
    input = stdin.readline
    k, _ = map(int, input().split())
    a = max(map(int, input().split()))
    print(max(0, 2 * a - k - 1))
main()

Python heapq

`python.py`


from sys import stdin

def main():
    import heapq
    input = stdin.readline
    input()
    a = [-1 * int(i) for i in input().split()]
    heapq.heapify(a)
    while len(a) > 1:
        u = heapq.heappop(a)
        v = heapq.heappop(a)
        if u + 1 < 0:
            heapq.heappush(a, u + 1)
        if v + 1 < 0:
            heapq.heappush(a, v + 1)
    if len(a) == 0:
        print(0)
    else:
        print(abs(a[0] + 1))
main()

Wenn die Operation kompliziert ist, ist es besser, eine Funktion für die Codekonvertierung vorzubereiten.