0w1

Yuki 489 株に挑戦 ( Sliding Window )

No.489 株に挑戦 - yukicoder

題意:
買賣股票,買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i <= D。求差額 * K,以及字典序最小的買賣日期。若無法得到正利潤,輸出 0 即可。

制約:
2 ≤ N ≤ 1e5
1 ≤ D < N
1 ≤ K ≤ 1e6
1 ≤ xi ≤ 1e6

解法:
努力寫了一次線段樹,但 python 也很給力的 TLE 了。
經典的滑動視窗:
window[ i ]: i - D ≤ window[ i ] < i 中最小的 window[ i ]。若不存在則為 -1。
用單調隊列維護下標的單調遞增和值的非嚴格單調遞增即可。

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

from collections import deque

N, D, K = map( int, input().split() )
X = list( int( input() ) for i in range( N ) )

window = [ -1 for i in range( N ) ]
dq = deque()
for i in range( N ):
  while len( dq ) and i - dq[ 0 ] > D:
    dq.popleft()
  if len( dq ):
    window[ i ] = dq[ 0 ]
  while len( dq ) and X[ i ] < X[ dq[ len( dq ) - 1 ] ]:
    dq.pop()
  dq.append( i )

best = 0
bl, br = -1, -1
for i in range( N ):
  if window[ i ] == -1: continue
  if [ best, bl ] >= [ X[ i ] - X[ window[ i ] ], - window[ i ] ]: continue
  best = X[ i ] - X[ window[ i ] ]
  bl, br = - window[ i ], i

print( best * K )
if best > 0:
  print( - bl, br )