POJ 3784 动态求中位数

输入若干个数，对第k个输入，如果k为奇数，则输出前k个数的中位数

这个题的方法应该非常多，hash+树状数组+二分

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
new Task().solve() ;
}
}
class Task{
InputReader in = new InputReader(System.in)
;
PrintWriter out = new PrintWriter(System.out)
;
final int N = 10008 ;
int[] bit = new int[N] ;
int limit ;
int lowbit(int x){
return x & (-x) ;
}
void add(int id , int c){
for( ; id <= limit ; id += lowbit(id)) bit[id] += c ;
}
int sum(int id){
int s = 0 ;
for( ; id > 0 ; id -= lowbit(id)) s += bit[id] ;
return s ;
}
int getMid(int h , int k){
int l = 1 , r = limit
, res = -1 ;
while(l <= r){
int m = (l + r) >> 1 ;
if(sum(m) >= k){
res = m ;
r = m - 1 ;
}
else l = m + 1 ;
}
return res ;
}
void solve(){
int t = in.nextInt() ;
while(t-- > 0){
int cas = in.nextInt() ;
int n = in.nextInt() ;
int[] a = new int[n] ;
int[] uni = new int[n] ;
Arrays.fill(bit , 0) ;
for(int i = 0 ; i < n
; i++) uni[i] = a[i] = in.nextInt() ;
Arrays.sort(uni) ;
uni = Std.unique(uni) ;
limit = uni.length ;
List<Integer> res = new ArrayList<Integer>() ;
for(int i = 0 ; i < n ; i++){
int h =
Std.upper_bound(uni, a[i]) ;
add(h, 1) ;
if((i&1) == 0){
int id = getMid(h, i/2 + 1 ) ;
res.add(uni[id-1]) ;
}
}
int m = (n+1) >> 1 ;
out.println( cas + " " + m )
;
for(int i = 0 ; i < m ; i++){
if(i % 10 == 0){
if(i > 0) out.println() ;
out.print(res.get(i)) ;
}
else out.print(" " + res.get(i)) ;
}
out.println() ;
}
out.flush() ;
}
}
class Std{
static int[] unique(int[] array , int left , int right){
if(left == right) return new int[]{array[left]} ;
int size = 1 ;
for(int i = left+1 ; i < right ; i++){
if(array[i] != array[i-1]) size++ ;
}
int[] res = new int[size] ;
int idx = 0 ;
res[idx++] = array[left] ;
for(int i = left+1 ;
i < right ; i++){
if(array[i] != array[i-1]) res[idx++] = array[i] ;
}
return res ;
}
static int[] unique(int[] array){
return unique(array , 0 , array.length) ;
}
static int upper_bound(int[] array , int l , int r , int val){
int res = r , m ;
r-- ;
while(l <= r){
m = (l + r) >> 1 ;
if(array[m] > val){
res = m ;
r = m - 1 ;
}
else l = m + 1 ;
}
return res ;
}
static int upper_bound(int[] array , int val){
return upper_bound(array , 0 , array.length , val) ;
}
}
class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = new StringTokenizer("");
}
private void eat(String s) {
tokenizer = new StringTokenizer(s);
}
public String nextLine() {
try {
return reader.readLine();
} catch (Exception e) {
return null;
}
}
public boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String s = nextLine();
if (s == null)
return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() {
return new BigInteger(next());
}
}

最后

以上就是健壮发带为你收集整理的POJ 3784 动态求中位数的全部内容，希望文章能够帮你解决POJ 3784 动态求中位数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。