題意：
? ? ?給你一串?dāng)?shù)字，然后給你最多進(jìn)行k次交換（只能交換相鄰的）問交換后的最小逆序數(shù)是多少。


思路：

? ? ?首先要知道的一個就是給你一個序列，每次只能交換相鄰的位置，把他交換成一個遞增序列所需要的最少步數(shù)等于整個序列的逆序數(shù)，在轉(zhuǎn)化到這個題目，我們只要求出個逆序數(shù)，然后輸出逆序數(shù) - k就行了，如果是負(fù)數(shù)輸出0。

#include<stdio.h> #include<string.h> #include<algorithm>#define N 100000 + 10 using namespace std;typedef struct {int num ,id; }NODE;NODE node[N];__int64 num[N]; int hash[N]; int lowbit(int x) {return x & -x; }void update(int x ,__int64 a ,int n) {for(int i = x ;i <= n ;i += lowbit(i))num[i] += a; }__int64 find(int x) {__int64 sum = 0;for(int i = x ;i > 0 ;i -= lowbit(i))sum += num[i];return sum; }bool camp(NODE a ,NODE b) {return a.num < b.num; }int main () {int n ,i ,a;__int64 m ,sum;while(~scanf("%d %I64d" ,&n ,&m)){for(i = 1 ;i <= n ;i ++){scanf("%d" ,&node[i].num);node[i].id = i;}sort(node + 1 ,node + n + 1 ,camp);int t = 0;node[0].num = -1;for(i = 1 ;i <= n; i ++){if(node[i].num != node[i-1].num)t ++; hash[node[i].id] = t;}memset(num ,0 ,sizeof(num));for(sum = 0 ,i = 1 ;i <= n ;i ++){sum += (i - 1) - find(hash[i]);update(hash[i] ,1 ,t);}if(sum < m) printf("0\n");else printf("%I64d\n" ,sum - m);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4911 简单树状数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。