Advertisement
Guest User

gigel

a guest
Nov 24th, 2014
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.22 KB | None | 0 0
  1. import java.util.Random;
  2. import java.util.Scanner;
  3.  
  4.  
  5.  
  6. class elem{
  7.     public int val;
  8.     public double pondere;
  9.    
  10.     elem(int v, double p){
  11.         val = v;
  12.         pondere = p;
  13.     }
  14.    
  15. }
  16.  
  17. public class Mediana {
  18.    
  19.     static elem[] v;
  20.  
  21.     public static void main(String[] args) {
  22.        
  23.         Scanner sc = new Scanner(System.in);
  24.        
  25.         int n = sc.nextInt();
  26.        
  27.         v = new elem[n];
  28.        
  29.         for (int i = 0; i < v.length; i++) {
  30.             v[i] = new elem(sc.nextInt(), sc.nextDouble());
  31.         }
  32.        
  33.         System.out.println(Divide(0, v.length - 1, 0, 0));
  34.        
  35.        
  36.        
  37.     }
  38.    
  39.     public static int Divide(int st, int dr, double Wst, double Wdr){
  40.        
  41.         if(st == dr){
  42.             return v[st].val;
  43.         }
  44.         Random rd = new Random();
  45.         int pivot = rd.nextInt(dr - st + 1);
  46.         pivot += st;
  47.        
  48.         double Ws = 0;
  49.         double Wd = 0;
  50.        
  51.         for(int i = st; i <= dr; i++){
  52.             if(i == pivot)
  53.                 continue;
  54.             if(v[i].val < v[pivot].val){
  55.                 Ws += v[i].pondere;
  56.             } else {
  57.                 Wd += v[i].pondere;
  58.             }
  59.         }
  60.         Ws += Wst;
  61.         Wd += Wdr;
  62.        
  63.         if(Ws <= 0.5 && Wd <= 0.5){
  64.             return v[pivot].val;
  65.         }
  66.        
  67.         else {
  68.             if(Ws > Wd){
  69.                 return Divide(st, pivot - 1, Wst, Wd + v[pivot].pondere);
  70.             } else {
  71.                 return Divide(pivot + 1, dr, Ws + v[pivot].pondere, Wdr);
  72.             }
  73.         }
  74.        
  75.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement