当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

线段树求逆序数(离散化)POJ 2299

发表于: 2012-12-06   作者:128kj   来源:转载   浏览:
摘要: POJ2299题意:   给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。例如将"91054"变成"01459",最小交换6次,如果直接暴力,会超时。 样例:(2次测试) Sample Input 5  序列中数的个数 9 1 0 5 4 3  序列中数
POJ2299题意:

  给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。例如将"91054"变成"01459",最小交换6次,如果直接暴力,会超时。


样例:(2次测试)
Sample Input

5  序列中数的个数
9
1
0
5
4
3  序列中数的个数
1
2
3
0   n=0结束

Sample Output

6
0


  其中需排序的数的范围0---999 999 999;显然数组不能开这么大,序列中数的个数N不大于500000,故先要将给出的序列离散到[1,500000]。

例: int a[] = {10000000, 10, 2000, 20, 300};
那么离散化后a[] = {5, 1, 4, 2, 3},是一个一一对应关系,而且满足原来的大小关系,离散的方法如下:
(1)定义一个类,用来表示序列中的一个数。
   class Node implements Comparable{
    int val;//值
    int no;//序号

     public int compareTo(Object o) {
      return this.val - ((Node) o).val;
  }
 }

(2)然后将所给序列用下面数组p表示,排序p并离散化.

            int data[] = new int[n];  
             Node[] p=new Node[n];
              
            for (int i = 0; i < n; i++) {   

              p[i]=new Node();
              p[i].val=in.nextInt();   
              p[i].no=i;   
            }

             Arrays.sort(p);
            for(int i=0;i<n;i++){
              data[p[i].no]=i+1;
           }//以上是使其离散化


POJ2299解题思路: 其实这题就是求这个序列的逆序数,离散化后用线段树边查询边插入即可。

下面是AC过的代码:(请参考: http://128kj.iteye.com/blog/1741183

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.io.BufferedInputStream; 
  
  
  class Seg_Tree {//线段树节点   
    int left,right;   
        int val;//区间内已插入的节点数   
    int calmid() {   
        return (left+right)/2;   
    }   
   }   
  
  class Node implements Comparable{
    int val;
    int no;

     public int compareTo(Object o) {
    return this.val - ((Node) o).val;
  }
 }
  public class Main{   
     private int LL(int x) { return x<<1;}  //两倍;   
     private int RR(int x) { return x<<1|1;} //两倍+1;   
     Seg_Tree tt[];   
    
  
    public Main(){   
      tt=new Seg_Tree[ 1048578];//用数组实现线段树   
      for(int i=0;i< 1048578;i++)   
          tt[i]=new Seg_Tree();   
    }   
  
    private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树   
    tt[idx].left = left;   
    tt[idx].right = right;   
    tt[idx].val = 0;   
    if(left == right) return ;     
    int mid = tt[idx].calmid();   
    build(left,mid,LL(idx));   
    build(mid+1,right,RR(idx));   
    }   
   
       
   private void insert(int aim,int l,int r,int k){  //将aim插入到线段树   
    if(tt[k].left==aim&&tt[k].right==aim) {   
      tt[k].val++;return ;   
    }     
     
    if(aim<=tt[k].calmid())    
       insert(aim,l,tt[k].calmid(),LL(k));     
    else        
      insert(aim,tt[k].calmid()+1,r,2*k+1);     
    tt[k].val=tt[LL(k)].val+tt[RR(k)].val;     
  }     
  
     
    //查询[left,right]中已插入的节点数   
    private int query(int left,int right,int idx){   
    if(left == tt[idx].left && right == tt[idx].right)    
           return tt[idx].val;   
       
    int mid = tt[idx].calmid();   
    if(right <= mid){   
        return query(left,right,LL(idx));   
    }    
       else if(mid < left) {   
        return query(left,right,RR(idx));   
    }    
       else {   
        return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));   
    }   
     }   
  
  public static void main(String[] args){   
   Scanner in = new Scanner(new BufferedInputStream(System.in));   
        while (in.hasNext()) {   
            int n = in.nextInt();   
            if (n == 0) {   
                break;   
            }   
          
            int data[] = new int[n];  
             Node[] p=new Node[n];
              
            for (int i = 0; i < n; i++) {   

              p[i]=new Node();
              p[i].val=in.nextInt();   
              p[i].no=i;   
            }

             Arrays.sort(p);
            for(int i=0;i<n;i++){
              data[p[i].no]=i+1;
           }//以上是使其离散化

          Main ma=new Main();   
          ma.build(1,n,1);   
          long sum = 0;     
          for(int i=0;i<n;i++){   
            sum += ma.query(data[i],n,1);//先查询   
            ma.insert(data[i],1,n,1);//后插入   
          }  
          System.out.println(sum);
        }  
    }
} 


源码:

线段树求逆序数(离散化)POJ 2299

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目链接:http://poj.org/problem?id=2299 Description In this problem, you have to analyze a p
Mayor's posters Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 34272 Accepted: 99
Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 44554 Accepted: 16
覆盖的面积 Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Picture Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Tota
Description The citizens of Bytetown, AB, could not stand that the candidates in the mayoral
Language: Default Antimonotonicity Time Limit: 2000MS Memory Limit: 65536K Total Submissions:
转自:http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464876.html POJ 1177 (线段树+离散化
线段树(Interval Tree)  线段树是一种二叉搜索树,将一个大区间划分成单元区间,每个单元区间对
Description In this problem, you have to analyze a particular sorting algorithm. The algorith
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号