[Bei Coder] Lösen Sie das ABC183 D-Problem mit Ruby

Der braune Codierer versuchte, das ABC183 D-Problem mit Ruby zu lösen.

Problem

Es gibt einen $ 1 $ Warmwasserbereiter, der $ W $ Liter heißes Wasser pro Minute liefern kann. Es gibt $ N $ Leute. Die $ i $ -te Person plant, jede Minute zwischen $ S_i $ und $ T_i $ (außer nur der Zeit $ T_i $) $ P_i $ Liter Wasser zu verwenden, das in diesem Warmwasserbereiter gekocht wird. Das heiße Wasser kühlt schnell ab und kann nicht gespeichert werden. Ist es möglich, alle wie geplant mit heißem Wasser zu versorgen?

Zwang

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 Alle Eingaben sind Ganzzahlen

Eingang

N　W S_1　T_1　P_1 ︙ S_N　T_N　P_N

Antworten

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

#Ein Array, das die pro Stunde verbrauchte Wassermenge speichert
a = Array.new(200005, 0)

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

    #Vorbereitung für "Array zum Speichern der kumulativen Summe"
    a[s] += p
    a[t] -= p
end

result = true

#Kumulative Summe speichern
200001.times do |i|
    if a[i] > w
        result = false
        break
    end
    a[i+1] += a[i]
end

puts result ? "Yes" : "No"

Denkweise

Verwenden Sie die kumulative Summe. Denken Sie jedoch daran, dass Sie dies später tun werden, nicht von Anfang an.

Bereiten Sie ein Array vor, um die pro Stunde verbrauchte Wassermenge zu speichern
Erhöhen oder verringern Sie die Wassermenge, die nur zu Beginn und am Ende des Gebrauchs verbraucht wird
Berechnen Sie die kumulierte Summe des Wasserverbrauchs für jede Stunde

Bereiten Sie ein Array vor, um die pro Stunde verbrauchte Wassermenge zu speichern

Da es sich um $ T_i \ leq 2 \ times 10 ^ 5 $ handelt, bereiten Sie ein Array mit $ 200001 $ oder mehr Elementen vor.

Erhöhen oder verringern Sie die Wassermenge, die nur zu Beginn und am Ende der Verwendung verwendet wird

Wie oben erwähnt, geht es zunächst nicht darum, die kumulative Summe zu berechnen. Wenn Sie von Anfang an danach fragen, wird Ihnen die Ausführungszeit ausgehen.

Wenn Sie Informationen für $ N $ Personen eingeben, erhöhen oder verringern Sie zunächst nur die Menge an Wasser, die zu Beginn und am Ende der Verwendung verbraucht wird. Gehen Sie insbesondere wie folgt vor.

Erhöhen Sie die Menge an Wasser, die Sie zu Beginn verwenden
Reduzieren Sie die am Ende des Gebrauchs verbrauchte Wassermenge

Berechnen Sie die kumulierte Summe des Wasserverbrauchs für jede Stunde

Danach berechnen wir die kumulierte Summe wie gewohnt. Es ist in Ordnung, wenn Sie beurteilen, ob es $ W $ überschreitet.

Impressionen

Ich habe von Anfang an nach der kumulierten Summe gefragt, konnte aber keine AC durchführen, da die Ausführungszeit nicht ausreichte. Weinen Erhöhen Sie die Menge an Wasser, die nur zu Beginn des Gebrauchs verbraucht wird, und verringern Sie sie erst am Ende des Gebrauchs. Ich sehe, ich fühle mich wie ich diese Hand hatte.