回分類題庫
h166: F.逆序數對
關鍵字: NPSC 2016 高中組初賽

測資點 : 3 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 64 Times / 58 Users | Submit : 243 Times / 71 Users | Accepted rate : 82%
題目加入時間 : 2017-11-03 11:50

Content: 简体中文

你拿到⼀個長度爲 N 的數列,你很好奇這個數列有什麼性質。但,你不知道這個數列中每個數字分別爲多少,你只知道這個數列中數字兩兩不同,此外,你還知道這個數列中相鄰元素的大小關係。

現在,你很想知道這個未知的數列"最少"會有多少組逆序數對。也就是,所有有著⼀樣相鄰元素大小關係的數列裡,逆序數對最少有幾組?

數列 a1, a2, . . . , aN 中的逆序數對就是⼀組 (i, j) ,滿足 1 ≤ i < j ≤ n 而且 ai > aj 。 

Input:

測試資料第一行會有一個正整數 T,代表總共有幾組測試資料。 

每組測試資料第一行會有一個正整數 N 代表未知的數列的長度。

每組測試資料第二行會有一個長度為 N − 1 並由 '>', '<' 組成的字串 s。s 的第 i 個字元代表未知數列第 i 項與第 i + 1 項的大小關係。

Output:

針對每組測資,輸出⼀⾏包含⼀個非負整數,代表該未知數列最少會有幾組逆序數對。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
4
><>
5
<<<<

Sample Output :

2
0

Hint :

Author :

NPSC 2016 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum