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 ≤ i < j ≤ n and ai > aj.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n，k (1 ≤ n ≤ 10 ^ 5，0 ≤ k ≤ 10 ^ 9). The second line contains n integers a1，a2，…，an (0 ≤ ai ≤ 10 ^ 9).
Output
For each tests:
A single integer denotes the minimum number of inversions.
Sample Input
3 1
2 2 1
3 0
2 2 1
Sample Output
1
2
思路
题目大概意思就是给定一串序列，在允许交换最多k次的情况下最后还有多少逆序对。 离散化 + 线段树，先计算出交换之前序列的逆序对数目sum，如果 sum > k结果就是 sum - k，否则sum < k结果就是0。坑点就是数据比较大用long long保存答案即可，整体时间复杂度O(nlogn)。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
const int maxn = 100005;
struct node{int x,pos;
}a[maxn];
ll s[maxn<<2];
bool cmp(node s1,node s2)
{if(s1.x == s2.x){ //一定要写，sort不稳定。可能导致错误return s1.pos < s2.pos;}else{return s1.x < s2.x;}
}
void update(int k,int l,int r,int ans)
{if(l == r){s[k] = 1;return ;} int m = (l+r)>>1;if(ans <= m){update(lson,ans);}else{update(rson,ans);}s[k] = s[k<<1] + s[k<<1|1];
}
ll query(int k,int l,int r,int ql,int qr)
{if(ql > r || qr < l){return 0;}if(ql <= l && r <= qr){return s[k];}int m = (l+r)>>1;ll ans = 0;ans += query(lson,ql,qr);ans += query(rson,ql,qr);return ans;
}
int main()
{int n,k;while(~scanf("%d%d",&n,&k)){for(int i = 1;i <= n;i++){scanf("%d",&a[i].x);a[i].pos = i;}sort(a+1,a+n+1,cmp);memset(s,0,sizeof(s));ll sum = 0;for(int i = 1;i <= n;i++){sum += query(1,1,n,a[i].pos,n);update(1,1,n,a[i].pos);} if(k >= sum){sum = 0;}else{sum -= k;}printf("%lld\n",sum);}return 0;
}
愿你走出半生，归来仍是少年~