作者:快乐健康美丽长寿tg | 来源:互联网 | 2023-06-06 18:53
归并排序求逆序数,然后ans-k与0取一个最大值就可以了。也可以用树状数组做,比赛的时候可能姿势不对,树状数组wa了、、InversionTimeLimit:2
归并排序求逆序数,然后ans-k与0取一个最大值就可以了。
也可以用树状数组做,比赛的时候可能姿势不对,树状数组wa了、、
Inversion
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 578 Accepted Submission(s): 249
Problem Description
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≤ii>aj.
Input
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).
Output
For each tests:
A single integer denotes the minimum number of inversions.
Sample Input
Sample Output
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include