第一屆內壢高中程式挑戰賽題目已公開 - 連結
永久計分板也已公開 - 連結
115 資訊學科能力競賽校內初賽題目已公開 - 連結
115 資訊學科能力競賽北二區複賽模擬賽題目已公開 - 第一場 - 第二場
永久計分板也已公開 - 連結
115 資訊學科能力競賽校內初賽題目已公開 - 連結
115 資訊學科能力競賽北二區複賽模擬賽題目已公開 - 第一場 - 第二場
107 . 國＊股還我錢！
TopCoder
Tags
Description
你得到了一份股價資料，總共有 $n$ 個數值，代表著從第 $1$ 天到第 $n$ 天的股票交易價格。
uu 想要你幫他看看，對於第 $i$ 天的價格，從第 $[1 ,\ i-1]$ 天中，最晚要哪一天買才不會虧。
如果第 $i$ 天必定會虧，輸出 -1。
對於所有測試資料：
$1 \le n \le 2 \times 10$$5$
$0 \le p_i \le 10$$9$
Input Format
輸入共 $2$ 行，
第一行共 $1$ 個數值，表示天數 $n$。
第二行共 $n$ 個數值，第 $i$ 個數字表示第 $i$ 天的股價。
Output Format
輸出僅 $1$ 行，
共 $n$ 個數值，第 $i$ 個數字表示對於第 $i$ 天的最晚交易的時機。
Sample Input 1
5 3 4 8 2 6
Sample Output 1
-1 1 2 -1 4
Hints
這 $n$ 天的股價 $p_{1} ,\ p_{2} , \dots ,\ p_{n}$，對於第 $i$ 天，需要從第 $[1 ,\ i-1]$ 天中找到最後一個比 $p_{i}$ 小或相等的價格，即為所求。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 1~3 | $n \le 10$$3$ | 15 |
| 3 | 1~8 | $p_{i} \le 10$$6$ | 25 |
| 4 | 4~16 | 題目範圍限制 | 60 |