Résolution en Ruby, Python et Java AtCoder ABC141 D Priority Queue

introduction

• Problèmes AtCoder * Utilise les recommandations pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Beginner Contest D - Powerful Discount Tickets Difficulty: 826

Ce thème, file d'attente prioritaire Ruby L'opération elle-même est simple, sortez l'article le plus cher de la file d'attente, appliquez un bon de réduction et remettez-le dans la file d'attente. Dans chaque cas, effectuez la même opération pour l'article le plus cher jusqu'à épuisement du ticket de réduction. Cependant, dans l'implémentation qui trie simplement comme suit, ce sera «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(:+)

Les files d'attente prioritaires vous permettent de trouver les éléments les plus chers avec moins de calcul que de tri. C'est «heapq» en Python et «PriorityQueue» en Java, mais ce n'est pas en Ruby, donc * Je veux implémenter Priority Queue en Ruby * J'ai emprunté le code à et l'ai légèrement modifié.

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

Même ceci est la dernière 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))

«Heapq» de Python prend la valeur minimale, vous devez donc ajouter un signe négatif. De plus, comme la division négative par «//» renvoie la valeur avec la valeur absolue la plus élevée, «ceil» est utilisé ici. 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 prend en charge la valeur maximale avec reverseOrder ().

Résumé

• Résolu ABC 141 D
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Familiarisez-vous avec Java

Site référencé

• Je souhaite implémenter la file d'attente prioritaire dans Ruby *
• [ruby] Implémentation de la file d'attente prioritaire *