TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

94.6% (247/261)

Submission's AC Ratio

50.1% (399/796)

Tags

Description

給你一個整數序列S: s1,s2,...,sn,我們說 si是這個序列的節點(Node)是因為所有在si之前的數 s1,s2,...,si-1都比 si還小,並且所有在si之後的數 si+1,si+2,...,sn都比 si還大。當然s1和sn都不是節點。

給你這樣的一個序列S,請問序列S中有幾個節點?

Input Format

Line 1: 測試資料組數 T (1<=T<=20)
Line 2~N+1:每一列為一組測試資料:第一個數字N (1<=N<=1,000,000) 代表序列S的長度,然後有N個整數s1,s2,...,sn,中間以一個空白間隔。
所有數字的絕對值都不會超過231-1。

Output Format

對於每一筆測試資料,請輸出該序列當中節點(Node)的個數。

Sample Input 1

1
8 1 3 2 4 6 7 5 8

Sample Output 1

1

Hints

範例測資說明:

只有4是節點,因為1,3,2都比4小;6,7,5,8都比4大。

註:

當然對於每一個數字,都可以花O(N)的時間掃描一次整個序列,得到其是否為節點的資訊。
但是這樣下來每筆測試資料執行的時間複雜度達到了O(N2),似乎有點太慢…

※2007/10/20補註:這個題目如果單純地使用cin的話時間會炸掉,因為輸入資料量太大了!

Problem Source

原TIOJ1017 / Problem Setter: Tmt

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 131072 262144 1