SRM 497 Div 1 Easy Permutation Signature

今次打開題目，從看懂到想出算法都很快，五分鐘內搞定。

題意﹕給了一個長度為N的字串S，而S只包含字元「I」或者「D」。請構造出一個1..N+1的排列P，使得如下條件成立。

1) S[i] = 'D': P[i] > P[i+1]
2) S[i] = 'I': P[i] < P[i+1]

P需要是lexicographically smallest。
若不存在則返回一個空的數組。

首先，大膽假設答案必然存在。快速瞄了一下example，好的，沒有No solution，猜想應該是對的。怎樣構建？
在紙筆寫了題目描述的樣例﹕

1 2 3 4 5 6 7
 D I I D I D

一開始的P必然滿足S[i] = 'I'。不滿足S[i] = 'D'的可以通過交換達成，即﹕

2 1 3 5 4 7 6
 D I I D I D

即是樣例答案。交換後仍無損S[i]='I'的特性，因為與通過交通的群組必然少於因為S[i]='I'而需要比對的數。亦因此推斷這樣的P是lexicographically smallest的。但，慢著，連續幾個的S[i]='D'怎辦？即時寫了另一組例子﹕

1 2 3 4 5 6
 D D I D D

答案明顯不過了–對於連續的'D'所涉及的數字，反轉就行。這也是因為需要符合DD..D的特性，亦根據之前的推論，這個答案仍是lexicographically smallest的。因此上述例子的答案如下﹕

3 2 1 6 5 4
 D D I D D

算法也是極其簡單的，只需先構建P[i] = i+1, 0<=i<=N，然後對於每一連續的'D'把其範圍內的數字反轉次序即成。