Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Random;
- import java.util.Scanner;
- class elem{
- public int val;
- public double pondere;
- elem(int v, double p){
- val = v;
- pondere = p;
- }
- }
- public class Mediana {
- static elem[] v;
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- v = new elem[n];
- for (int i = 0; i < v.length; i++) {
- v[i] = new elem(sc.nextInt(), sc.nextDouble());
- }
- System.out.println(Divide(0, v.length - 1, 0, 0));
- }
- public static int Divide(int st, int dr, double Wst, double Wdr){
- if(st == dr){
- return v[st].val;
- }
- Random rd = new Random();
- int pivot = rd.nextInt(dr - st + 1);
- pivot += st;
- double Ws = 0;
- double Wd = 0;
- for(int i = st; i <= dr; i++){
- if(i == pivot)
- continue;
- if(v[i].val < v[pivot].val){
- Ws += v[i].pondere;
- } else {
- Wd += v[i].pondere;
- }
- }
- Ws += Wst;
- Wd += Wdr;
- if(Ws <= 0.5 && Wd <= 0.5){
- return v[pivot].val;
- }
- else {
- if(Ws > Wd){
- return Divide(st, pivot - 1, Wst, Wd + v[pivot].pondere);
- } else {
- return Divide(pivot + 1, dr, Ws + v[pivot].pondere, Wdr);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement