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
先用树状数组求出逆序数。因为每一次交换可以增加或着减少一对逆序数，假设有m对逆序数，我们交换n对，那么这n对我们让他每次都减少一对逆序数，交换n次后 还有m - n对
逆序。注意题目中k的取值，如果求出的逆序数大于k，那么可以直接得出结果 res - k ，如果小于k，此时就要注意数字串中是否有重复的，如果没有那么当交换res - k次后
此时逆序数恰好为0， 剩余交换次数为k - res，如果k - res为偶数，那么我们可以重复交换同一对此时逆序数还为0，如果为奇数，此时只能结果为1。 如果字串中有重复的
那么可以交换那两个重复的数，此时无论是奇数还是偶数，结果并不影响最小逆序对总数。
/*=============================================================================## Author: liangshu - cbam ## QQ : 756029571 ## School : 哈尔滨理工大学 ## Last modified: 2015-08-30 22:32## Filename: A.cpp## Description: # The people who are crazy enough to think they can change the world, are the ones who do ! =============================================================================*/##include<iostream>#include<sstream>#include<algorithm>#include<cstdio>#include<string.h>#include<cctype>#include<string>#include<cmath>#include<vector>#include<stack>#include<queue>#include<map>#include<set>using namespace std;#define maxn 100010struct node{ int v,id;} s[maxn];int c[maxn],n;typedef long long ll;ll res;bool cmp(node x,node y){ return ((x.v>y.v) || ((x.v==y.v)&&(x.id>y.id)));}int Lowbit(int x){ return x&(x^(x-1));}ll Getsum(int pos){ ll ret = 0LL; while(pos>0) { ret+=c[pos]; pos -= Lowbit(pos); } return ret;}ll update(int pos){ while(pos<=n) { c[pos]++; pos+=Lowbit(pos); }}int main(){ int k,x; int cs = 1; while(scanf("%d%d",&n,&k)!=EOF) { set<int>cnt; memset(c,0,sizeof(c)); res = 0; for(int i=1; i<=n; i++) { scanf("%d",&s[i].v); cnt.insert(s[i].v); s[i].id = i; } sort(s+1,s+n+1,cmp); for(int i=1; i<=n; i++) { res += Getsum(s[i].id); update(s[i].id); } if((res-k)>=0) printf("Case #%d: %lld\n",cs ++,res-k); else { if(cnt.size() < n) { printf("Case #%d: 0\n",cs ++); } else { if(abs(res-k)%2) printf("Case #%d: 1\n",cs ++); else printf("Case #%d: 0\n",cs ++); } } } return 0;}