1347 - Reverse Number
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 547
Solved: 116
- Description
- Given a non-negative integer sequence A with length N, you can exchange two adjacent numbers each time. After K exchanging operations, what’s the minimum reverse number the sequence can achieve?
The reverse number of a sequence is the number of pairs (i, j) such that
i < j and Ai > Aj
- Input
- There are multiple cases.
For each case, first line contains two numbers: N, K
2<=N<=100000, 0 <= K < 2^60
Second line contains N non-negative numbers, each of which not greater than 2^30
- Output
- Minimum reverse number you can get after K exchanging operations.
- sample input
-
3 1 3 2 1 5 2 5 1 4 3 2
- sample output
-
Case #1: 2 Case #2: 5
- hint
- source
- Liu Fei, HUST Campus 2009