`
128kj
  • 浏览: 601186 次
  • 来自: ...
社区版块
存档分类
最新评论

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

阅读更多
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);
        }  
    }
} 


源码:
1
2
分享到:
评论
3 楼 128kj 2012-12-06  
不好意思,没写清题目意思,已改过来了。
  给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。
2 楼 mfkvfn 2012-12-06  
引用
例如将"91054"变成"01459",最小交换6次


我怎么觉得只要两次就可以了

91054   第一次交换9和0,得到01954
01954   第二次交换9和4,得到01459
1 楼 HalfSmoked 2012-12-06  
引用
例如将"91054"变成"01459",最小交换6次

我怎么感觉是交换两次就行了。9和0和4.

相关推荐

    利用线段树求逆序数(JAVA)

    在这个场景中,我们使用线段树来求解逆序数,可以实现O(n log n)的时间复杂度,其中n是数组的长度。线段树通过将数组分割成一系列连续的子区间,并为每个子区间维护一些信息,可以快速地查询或修改这些区间的信息。 ...

    归并排序求逆序数

    ### 归并排序求逆序数 #### 一、引言 在计算机科学与数据结构领域,排序算法是基础且重要的组成部分。其中,归并排序作为一种高效稳定的排序方法,在实际应用中有着广泛的应用场景。本篇文章将围绕如何利用归并...

    分治法求逆序数

    求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。

    求逆序数对1

    POJ 2299 是一个经典的逆序数对算法题目,它要求计算一个序列中的逆序数对数量。该问题可以使用多种算法解决,包括暴力枚举、归并排序、树状数组等。 暴力枚举算法 暴力枚举算法是最简单的解决方法,它通过枚举...

    POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】

    在`POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】.cpp`文件中,你应该能够找到使用归并排序算法计算逆序对的实现。这种方法相比于直接求解,虽然增加了额外的排序操作,但大大提高了时间效率,尤其在处理大...

    mergeSort 求逆序数对matlab代码

    算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅

    利用归并排序求逆序数

    利用归并排序求逆序数,复杂度在O(nlgn)含测试用例

    算法-求排列的逆序数(信息学奥赛一本通-T1237).rar

    《算法-求排列的逆序数(信息学奥赛一本通-T1237)》这个主题涉及到的是计算机科学中的一个重要概念,逆序对或逆序数,它在算法设计和分析中扮演着关键角色,特别是在解决排序和组合优化问题时。逆序数是衡量一个...

    js_leetcode-求逆序数

    求逆序数 求逆序数 求逆序数 求逆序数 求逆序数

    求数组的逆序数

    在计算机科学和编程领域,"数组的逆序数"是一个重要的概念,特别是在算法分析和排序算法中。逆序数(Inversion Count)是指在数组或序列中,如果一个大于其后面的元素,则这样的对称为逆序对。逆序数就是数组中逆序...

    线段树完整版

    - **解决思路**: 使用线段树来维护区间内的逆序对数量,通过动态规划的方法来求解最小逆序数。 - **关键步骤**: - 定义线段树节点存储区间内的逆序对数量。 - 构建线段树,维护区间内的逆序对数量。 - 对于每次...

    POJ 2299_AC

    在这里要用到__int64,也就是long long int

    分治法求数组中的逆序数

    有一实数序列a1,a2,....an,若i且ai&gt;aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。

    归并求逆序对 C语言实现

    ### 归并求逆序对 C语言实现 #### 知识点详解 1. **归并排序算法**:归并排序是一种经典的排序算法,采用分治策略来对数组进行排序。其基本思想是将待排序的数据分成两部分,分别对这两部分数据进行排序,然后再...

    学习电脑信息用while循环获得逆序数

    学习电脑信息用while循环获得逆序数 在计算机编程中,while循环是一种常用的循环结构,可以用来实现各种复杂的算法。今天,我们将学习如何使用while循环来获得逆序数。 什么是逆序数?逆序数是指将一个数字的各个...

    线段树题目

    - **POJ 1151**:结合了线段树和离散化的技巧来求解矩形面积的并集。这需要对输入的坐标进行离散化处理,以减少空间复杂度,并使用线段树维护区间信息。 - **POJ 1177**:求解矩形周长的并集。此题与POJ 1151类似,...

    线段树的合并_黄嘉泰.pptx

    这意味着,如果我们对同一序列进行多次操作,可以利用这一特性来优化算法,例如通过持久化线段树来避免重复计算。 线段树的合并操作是其独特之处,它可以用来高效地处理一系列合并操作,如在POI18 rot题目中,解决...

    算法-求逆序对(信息学奥赛一本通-T1311).rar

    - 在合并两个大小分别为m和n的已排序子数组时,遍历每个元素,统计小于当前元素的元素个数,这个数量就是逆序对。 - 归并排序的总时间复杂度为O(n log n),其中n是数组的长度。 2. **树状数组(斐波那契堆)**: ...

    线段树汇总

    - Atlantis(1151):经典的扫描线求矩形面积交,通过离散化和线段树实现。 - Picture(1177):要求求解矩形周长的并,需要维护线段树中的多个信息。 - K-th Number(2155):使用线段树维护归并排序树,并采用...

    求逆序数的C语言实现.docx

    求逆序数的C语言实现.docx

Global site tag (gtag.js) - Google Analytics