Let a1, a2, …, an be a permutation of {1, 2, …, n} and n smaller than 100. For a pair (ai, aj), if i < j and ai > aj, then (ai, aj) induces an inversion. For example, in the permutation 2, 4, 1, 3, 5, there are three inversions, i.e., (2, 1), (4, 1) and (4, 3). Given a permutation π of {1, 2, … , n}, please write a program to compute the number of inversions in π .
令a1, a2, ..., an為{1, 2, ..., n}且n小於100的排列。對於一個配對(ai, aj)，如果i < j且ai > aj，則(ai, aj)形成一個逆序。 例如，在排列2, 4, 1, 3, 5中，存在三個逆序，即(2, 1), (4, 1)和(4, 3)。給定一個{1, 2, ..., n}的排列π，請撰寫一個程式來計算π中的逆序數。
The first line contains an integer m indicating the number of test cases.
Each test case consists of two lines. The first line contains an integer n indicating the length of the permutation. The second line contains n distinct numbers ranging from 1 to n, and any two numbers are separated by a space.
輸入的第一行的整數m表示測試案例的數量。
每個測試案例由兩行組成。第一行的整數n表示數字序列的長度；第二行則為n個數字落在[1, n]間的數字序列，且任意兩個數字之間用空格分隔。
The output contains m lines, where one line is for one test case.
Each line shows the number of inversions of the corresponding permutation.
每個測試案例的輸出包含一行。每行顯示輸入排列的逆序次數。
3 5 3 5 4 2 1 10 4 1 9 5 6 3 2 7 8 10 6 2 6 5 4 1 3
8 14 10
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||