2448: Inversion
内存限制:128 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
bobo has a sequence a1,a2,…,an. He is allowed to swap two adjacent numbers for no more than k times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and ai>aj.
输入
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
输出
For each tests:
A single integer denotes the minimum number of inversions.
样例输入 复制
3 1
2 2 1
3 0
2 2 1
样例输出 复制
1
2