[At Coder] Résolvez le problème ABC183 D avec Ruby

Le codeur marron a tenté de résoudre le problème ABC183 D avec Ruby.

problème

AtCoder Beginner Contest 183

D - Water Heater

Il y a un chauffe-eau à 1 $ qui peut fournir $ W $ litres d'eau chaude par minute. Il y a des gens $ N $. La $ i $ ème personne prévoit d'utiliser $ P_i $ litres d'eau bouillie dans ce chauffe-eau toutes les minutes entre le moment $ S_i $ et $ T_i $ (à l'exclusion du temps $ T_i $). L'eau chaude refroidit rapidement et ne peut pas être stockée. Est-il possible de fournir de l'eau chaude à tous comme prévu?

Contrainte

1 \leq N \leq 2 \times 10^5 0 \leq S_i \leq 2 \times 10^5 1 \leq W, P_i \leq 10^9 Toutes les entrées sont des entiers

contribution

N W S_1 T_1 P_1S_N T_N P_N

Répondre

nw = gets.chomp.split.map(&:to_i)
n = nw[0]
w = nw[1]

#Un tableau qui stocke la quantité d'eau utilisée par heure
a = Array.new(200005, 0)

n.times do
    stp = gets.chomp.split.map(&:to_i)
    s = stp[0]
    t = stp[1]
    p = stp[2]

    #Préparation du "tableau pour stocker la somme cumulée"
    a[s] += p
    a[t] -= p
end

result = true

#Stocker la somme cumulée
200001.times do |i|
    if a[i] > w
        result = false
        break
    end
    a[i+1] += a[i]
end

puts result ? "Yes" : "No"

Façon de penser

Utilisez la somme cumulée. Cependant, gardez à l'esprit que vous le ferez plus tard, pas depuis le début.

  1. Préparez un tableau pour stocker la quantité d'eau utilisée par heure
  2. Augmentez ou diminuez la quantité d'eau utilisée uniquement au début et à la fin de l'utilisation
  3. Calculez la somme cumulée de la consommation d'eau pour chaque heure

Préparez un tableau pour stocker la quantité d'eau utilisée par heure

Comme c'est $ T_i \ leq 2 \ fois 10 ^ 5 $, préparez un tableau avec 200001 $ ou plus d'éléments.

Augmenter ou diminuer la quantité d'eau utilisée uniquement au début et à la fin de l'utilisation

Comme mentionné ci-dessus, il ne s'agit pas de calculer la somme cumulée dans un premier temps. Si vous le demandez depuis le début, vous manquerez de temps d'exécution.

Tout d'abord, lors de la saisie d'informations pour des personnes $ N $, augmentez ou diminuez uniquement la quantité d'eau utilisée au début et à la fin de l'utilisation. Plus précisément, procédez comme suit.

--Augmentez la quantité d'eau utilisée lorsque vous commencez à utiliser --Réduire la quantité d'eau utilisée en fin d'utilisation

Calculez la somme cumulée de la consommation d'eau pour chaque heure

Après cela, nous calculerons la somme cumulée comme d'habitude. Ce n'est pas grave si vous jugez s'il dépasse $ W $.

Impressions

Je suis allé demander la somme cumulée depuis le début, mais je n'ai pas pu AC car le temps d'exécution n'était pas suffisant. Pleurs Augmentez la quantité d'eau utilisée uniquement en début d'utilisation et diminuez-la uniquement en fin d'utilisation. Je vois, j'ai l'impression d'avoir cette main.

Recommended Posts

[At Coder] Résolvez le problème ABC183 D avec Ruby
[At Coder] Résolvez le problème ABC182 D avec Ruby
[Competition Pro] Résolvez les problèmes de sac à dos avec Ruby
AtCoder ABC127 D hash à résoudre avec Ruby 2.7.1
[Débutant] Résolvons le problème d'AtCoder avec Ruby en regardant l'article!
J'ai essayé de résoudre le problème de la "sélection multi-étapes" avec Ruby
[Chez Coder] Présentation de Competitive Pro avec Ruby
J'ai essayé de résoudre le problème de la séquence Tribonacci en Ruby, avec récurrence.
Problème atcoder ABC70 D
Tableau 2D AtCoder ABC129 D résolu en Ruby et Java
Résolvez le problème du logarithme discret avec un mod arbitraire
Résolvons le problème FizzBuzz!
[Ruby] problème avec l'instruction if
Programmation avec ruby (en route)
Résoudre la moyenne multiset ARC104 D avec Scala, Java, C ++, Ruby, Perl, Elixir
Résoudre le problème du sac à dos avec une planification dynamique
J'ai essayé de résoudre le problème de la séquence Tribonacci en Ruby (temps limite 10 minutes)
Problème de rubis ⑦
[Ruby] Définissez la hiérarchie en même temps que l'initialisation de Hash avec la méthode tap
Publiez l'application avec ruby on rails
Gérez la version de Ruby elle-même avec rbenv
Un rapide coup d'œil sur le problème de Monty Hall
Déterminez la page actuelle avec Ruby on Rails
[Java] Essayez de résoudre le problème de Fizz Buzz
J'ai vérifié le nombre de taxis avec Ruby