ARC 072 F - Dam ( Greedy, Monotonous, Deque )

F: Dam - AtCoder Regular Contest 072 | AtCoder

題意：
有一個水壩，容量是 L。有 N 天，第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩，晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i，問使得第 i 天恰有容量 L 的水在水壩裡的前提下，第 i 天最大可能的溫度。注意，任意時刻都不能使得水壩裡的水超過 L。溫度的變化根據理想的物理原則。

制約：
1≦N≦5e5
1≦L≦1e9
0≦ti≦1e9(1≦i≦N)
1≦vi≦L(1≦i≦N)
v1=L
L,vi,ti は整数である

解法：
大致上是要盡量讓冷的水優先流去。
考慮進來的水總是對於溫度單調遞增的，那麼顯然從前面的貪心流出即可。
問題是如果某一天進來的水，比那之前的水冷的時候，先等待混合後再流出一定比較好。
因此維護一個單調隊列，由左至右是時間遞增，當要用一個新的天的水更新時，只要隊尾的溫度比當前這個水的溫度高就不斷進行合併。
需要流出去時從隊首一一排出即可。

時間 / 空間複雜度：
O( N )

from collections import deque

N, L = map( int, input().split() )
T = []
V = []
for i in range( N ):
  t, v = map( int, input().split() )
  T.append( t )
  V.append( v )

dq = deque()
ct, cv = 0.0, 0.0
for i in range( N ):
  while cv + V[ i ] > L:
    ft, fv = dq[ 0 ]
    take = min( cv + V[ i ] - L, fv )
    ct, cv = ( ct * cv - ft * take ) / ( cv - take ), cv - take
    if take == fv:
      dq.popleft()
    else:
      dq[ 0 ] = [ ft, fv - take ]
  ct, cv = ( ct * cv + T[ i ] * V[ i ] ) / L, L
  print( "%.7f" % ct )
  while len( dq ):
    bt, bv = dq[ len( dq ) - 1 ]
    if bt < T[ i ]: break
    T[ i ], V[ i ] = ( T[ i ] * V[ i ] + bt * bv ) / ( V[ i ] + bv ), V[ i ] + bv
    dq.pop()
  dq.append( [ T[ i ], V[ i ] ] )