[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

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_1 ︙ S_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.

Préparez un tableau pour stocker la quantité d'eau utilisée par heure
Augmentez ou diminuez la quantité d'eau utilisée uniquement au début et à la fin de l'utilisation
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.