首页 > 专题系列 > Java解POJ > POJ 2104 K-th Number [解题报告] Java
2013
11-10

POJ 2104 K-th Number [解题报告] Java

K-th Number

问题描述 :

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.

That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i...j] segment, if this segment was sorted?”

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

输入:

The first line of the input file contains n — the size of the array, and m — the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).

The second line contains n different integer numbers not exceeding 109 by their absolute values — the array for which the answers should be given.

The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

输出:

For each question output the answer to it — the k-th number in sorted a[i...j] segment.

样例输入:

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

样例输出:

5
6
3

温馨提示:

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.Arrays;
class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss=in.readLine().split(" ");
  int a=Integer.parseInt(ss[0]);
  int k=Integer.parseInt(ss[1]);
  my[] p=new my[a];
  ss=in.readLine().split(" ");
  for(int i=0;i< a;i++)
	p[i]=new my(i,Integer.parseInt(ss[i]));
  Arrays.sort(p);
  while((k--)!=0)
   {
	ss=in.readLine().split(" ");
	int l=Integer.parseInt(ss[0])-1;
	int r=Integer.parseInt(ss[1]);
	int cnt=Integer.parseInt(ss[2]);
	for(int i=0;i< a;i++)
	{
          if(p[i].num>=l&&p[i].num< r)
	   {
	    cnt--;
	    if(cnt==0)
	     {
		System.out.println(p[i].t);
		break;
	     }
	   }
	}
     }
   }

 }

 class my implements Comparable< my>
 {
	int num,t;
	public my(int a,int b)
	{
		num=a;
		t=b;
	}
	public int compareTo(my arg0) {
		return t-arg0.t;
	}
}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  4. [email protected]