hdu 2689 Sort it

点击打开链接hdu2689

思路：线段树+单点更新
分析：
1 题目给定n个数要求最少的交换次数使得序列有序
2 显然两个数要交换肯定是满足i < j && num[i] > num[j]。那么假设现在读入一个数num[i]，我们要求这个数num[i]要和前面的交换几次使得序列有序，就是查找num[0]~num[i-1]之间比num[i]大的数的个数，那么这个过程我们就可以利用线段树的查找，我们只要去查找[num[i]+1 ， n]这个区间已经插入的个数即可，然后更新线段树
3 注意当num[i] == n的时候不用查找，直接更新

4 题目给定n 最大为1000，那么最话的情况下次数是1+2+3+...n，那么不会超过int。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 1010

int n;
struct Node{
   int left;
   int right;
   int num;
};
Node node[4*MAXN];

//建立一颗空的线段树
void buildTree(int left , int right , int pos){
   node[pos].left = left;
   node[pos].right = right;
   node[pos].num = 0;
   if(left == right)
     return;
   int mid = (left+right)>>1;
   buildTree(left , mid , pos<<1);
   buildTree(mid+1 , right , (pos<<1)+1);
   node[pos].num = node[pos<<1].num + node[(pos<<1)+1].num;
}

//询问
int query(int left , int right , int pos){
   if(node[pos].left == left && node[pos].right == right)
      return node[pos].num;
   int mid = (node[pos].left + node[pos].right)>>1;
   if(right <= mid)
      return query(left , right , pos<<1);
   else if(left > mid)
      return query(left , right , (pos<<1)+1);
   else
      return query(left , mid , pos<<1)+query(mid+1 , right , (pos<<1)+1);
}

//更新
void update(int index , int pos){
   if(node[pos].left == node[pos].right){
      node[pos].num++;
      return;
   }
   int mid = (node[pos].left + node[pos].right)>>1;
   if(index <= mid)
     update(index , pos<<1);
   else
     update(index , (pos<<1)+1);
   node[pos].num = node[pos<<1].num+node[(pos<<1)+1].num;
}

int main(){
   int x , ans;
   while(scanf("%d" , &n) != EOF){
      buildTree(1 , n , 1);
      ans = 0;
      for(int i = 1 ; i <= n ; i++){
         scanf("%d" , &x);
         if(x != n)
           ans += query(x+1 , n , 1);
         update(x , 1);
      }
      printf("%d\n" , ans);
   }
   return 0;
}

思路：树状数组
分析：
1 题目给定n个数要求最少的交换次数使得序列有序序列
2 显然两个数要交换肯定是满足i < j && num[i] > num[j]。那么假设现在读入一个数num[i]，我们要求这个数num[i]要和前面的交换几次使得序列有序，就是查找num[0]~num[i-1]之间比num[i]大的数的个数。那么如果我们用树状数组来做的话，读入num[i]的时候我们应该查找前i-1个数比num[i]大的数，那么个数就是i-1-getSum(x-1)，当x为1的时候就是i-1。最后更新树状数组。（这里原数组A[I]表示的是i是否插入，A[i]的值只有0/1两种!）

3 题目给定n 最大为1000，那么最话的情况下次数是1+2+3+...n，那么不会超过int。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 1010

int num[MAXN];
int C[MAXN];

int lowbit(int x){
   return x&(-x);
}

int getSum(int x){
   int sum = 0;
   while(x > 0){
      sum += C[x];
      x -= lowbit(x);
   }
   return sum;
}

void update(int x){
   while(x <= MAXN){
      C[x] += 1;
      x += lowbit(x);
   }
}

int main(){
   int x , ans , n;
   while(scanf("%d" , &n) != EOF){
      memset(num , 0 , sizeof(num));
      memset(C , 0 , sizeof(C));
      ans = 0;
      for(int i = 1 ; i <= n ; i++){
         scanf("%d" , &x);
         if(x > 1)
           ans += i-1-getSum(x-1);
         else
           ans += i-1;
         update(x);//更新树状数组
      }
      printf("%d\n" , ans);
   }
   return 0;
}