1080 . A.逆序數對

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

84.1% (666/792)

Submission's AC Ratio

24.6% (1394/5661)

Tags

data-structures divide-and-conquer sorting

Description

對一個數列 S 來說，若 S 的第 i 項 si 與第 j 項 sj 符合 si>sj，並且 i<j 的話，那麼我們說 (i,j) 是一個逆序數對。請問給定 S，總共有多少個逆序數對呢？

Input Format

輸入檔可能包含多筆測試資料，每筆測試資料第一列會有一個正整數 n （1≤n≤105），第二列有 n 個整數依序為數列 S 的每一項，以一個空白隔開。當 n=0 的時候代表輸入結束，你不必對這筆資料作處理。所有數字都可以用有號32-bit整數型態儲存。

Output Format

對於每組測試資料請先輸出這是第幾個序列，然後是該序列的逆序數對的總數。請參考Sample Output。

Sample Input 1

5
1 2 3 4 5
5
1 2 3 5 4
0

Sample Output 1

Case #1: 0
Case #2: 1

Hints

註：請盡量不要使用cin處理輸入，否則極有可能會TLE。

Problem Source

原TIOJ1080 / 經典問題練習。Problem Setter: Tmt。
2021.03.01 Update: Added LATEX by FHVirus

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
Submit
Back to Top