Lösen in Ruby, Python und Java AtCoder ABC141 D Priority Queue

Einführung

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

Dieses Thema

AtCoder Beginner Contest D - Powerful Discount Tickets Difficulty: 826

Dieses Thema, Prioritätswarteschlange Ruby Der Vorgang selbst ist einfach: Nehmen Sie den teuersten Artikel aus der Warteschlange, legen Sie einen Rabattgutschein ein und stellen Sie ihn wieder in die Warteschlange. Führen Sie in jedem Fall den gleichen Vorgang für den teuersten Artikel aus, bis das Rabattticket aufgebraucht ist. In der Implementierung, die einfach wie folgt sortiert wird, ist es jedoch "TLE".

ruby_tle.rb

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
a.sort_by!{|x| -x}
m.times do
  b = a.shift
  b /= 2
  a << b
  a.sort_by!{|x| -x}  
end
puts a.inject(:+)

Mit Prioritätswarteschlangen können Sie die teuersten Elemente mit weniger Rechenaufwand als beim Sortieren finden. Es ist "Heapq" in Python und "PriorityQueue" in Java, aber nicht in Ruby, also * Ich möchte Priority Queue in Ruby implementieren * Ich habe den Code von ausgeliehen und ein wenig geändert.

ruby.rb

class PriorityQueue
  def initialize(array = [])
    @data = []
    array.each{|a| push(a)}
  end

  def push(element)
    @data.push(element)
    bottom_up
  end

  def pop
    if size == 0
      return nil
    elsif size == 1
      return @data.pop
    else
      min = @data[0]
      @data[0] = @data.pop
      top_down
      return min
    end
  end

  def size
    @data.size
  end

  private

  def swap(i, j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def parent_idx(target_idx)
    (target_idx - (target_idx.even? ? 2 : 1)) / 2
  end

  def bottom_up
    target_idx = size - 1
    return if target_idx == 0
    parent_idx = parent_idx(target_idx)
    while (@data[parent_idx] > @data[target_idx])
      swap(parent_idx, target_idx)
      target_idx = parent_idx
      break if target_idx == 0
      parent_idx = parent_idx(target_idx)
    end
  end

  def top_down
    target_idx = 0

    while (has_child?(target_idx))

      a = left_child_idx(target_idx)
      b = right_child_idx(target_idx)

      if @data[b].nil?
        c = a
      else
        c = @data[a] <= @data[b] ? a : b
      end

      if @data[target_idx] > @data[c]
        swap(target_idx, c)
        target_idx = c
      else
        return
      end
    end
  end

  # @param Integer
  # @return Integer
  def left_child_idx(idx)
    (idx * 2) + 1
  end

  # @param Integer
  # @return Integer
  def right_child_idx(idx)
    (idx * 2) + 2
  end

  # @param Integer
  # @return Boolent
  def has_child?(idx)
    ((idx * 2) + 1) < @data.size
  end
end

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
e = a.map{|x| -x}
b = PriorityQueue.new(e)
m.times do
  c = b.pop
  b.push(-(-c / 2))
end
ans = 0
while b.size > 0
  ans -= b.pop
end
puts ans

Auch dies ist die letzte Minute. Python

python.py

import heapq
import math

n, m = map(int, input().split())
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for _ in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a, math.ceil(b / 2))
print(-1 * sum(a))

Pythons heapq nimmt den Mindestwert an, daher müssen Sie ein negatives Vorzeichen hinzufügen. Da die negative Division durch "//" den Wert mit dem größeren absoluten Wert zurückgibt, wird hier auch "Ceil" verwendet. 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());
        int M = Integer.parseInt(sc.next());
        PriorityQueue<Long> A = new PriorityQueue<>(Collections.reverseOrder());
        for (int i=0; i<N; i++) {
            A.add(Long.parseLong(sc.next()));
        }
        sc.close();

        for (int i=0; i<M; i++) {
            long new_price = (long)A.poll()/2;
            A.add(new_price);
        }

        long sum = 0;
        for (long a : A) {
            sum += a;
        }
        System.out.println(sum);
    }
}

        PriorityQueue<Long> A = new PriorityQueue<>(Collections.reverseOrder());

Java unterstützt den Maximalwert mit reverseOrder ().

Zusammenfassung

• Gelöstes ABC 141 D.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut
• Machen Sie sich mit Java vertraut

Referenzierte Site

• Ich möchte Priority Queue in Ruby implementieren *
• [ruby] Implementierung der Prioritätswarteschlange *