2022-07-01: at the annual meeting of a company, everyone is going to play a game of giving bonuses. There are a total of N employees. Each employee has construction points and trouble points. They nee

2022-07-01： At the annual meeting of a company , Everyone is going to play the game of one food bonus , Altogether n Employees ,

Every employee has construction points and trouble points ,

They need to line up , The boss must be at the front of the team , The boss also has construction points and trouble points ,

When you're in line , All employees will receive their own bonuses ,

The employee's bonus = The construction integral product of everyone in front of him / The employee's own trouble points , Rounding down ,

For the sake of fairness ( Farting ), The boss hopes : Let the employee who gets the highest bonus , Get as little bonus as possible ,

So I want you to help him rearrange the line , Return to the employee with the highest bonus 、 The minimum amount of bonus .

During the Kwai exam , Given the amount of data , Full array of code can also pass ！

1 <= n <= 1000, 1<= integral <= 10000;

From Ali .

answer 2022-07-01：

Line segment tree + Hashtable + Dichotomy .

The code to use rust To write . The code is as follows ：

use rand::Rng;
use std::collections::HashMap;
fn main() {
    let n: isize = 9;
    let v: isize = 50;
    let test_time: i32 = 5000;
    println!(" Beginning of the test ");
    for i in 0..test_time {
        let a = rand::thread_rng().gen_range(0, v) + 1;
        let b = rand::thread_rng().gen_range(0, v) + 1;
        let len = rand::thread_rng().gen_range(0, n);
        let mut value = random_array(len, v);
        let mut trouble = random_array(len, v);
        let ans1 = most_min1(a, b, &mut value, &mut trouble);
        let ans2 = most_min2(a, b, &mut value, &mut trouble);
        if ans1 != ans2 {
            println!(" Something went wrong !{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!(" End of test ");
}

//  Violence method 
//  In order to verify 
// a :  Contribution points of the boss 
// b :  Boss's trouble points 
// value[i] : i Contribution points of employee No 
// trouble[i] : i Trouble points of employee No 
//  return  :  The employee with the highest bonus gets 、 The minimum amount of bonus 
fn most_min1(a: isize, _: isize, value: &mut Vec<isize>, trouble: &mut Vec<isize>) -> isize {
    return process1(a, value, trouble, 0);
}

fn process1(boss: isize, value: &mut Vec<isize>, trouble: &mut Vec<isize>, index: isize) -> isize {
    if index == value.len() as isize {
        let mut value_all = boss;
        let mut ans = 0;
        for i in 0..value.len() as isize {
            ans = get_max(ans, value_all / trouble[i as usize]);
            value_all *= value[i as usize];
        }
        return ans;
    } else {
        let mut ans = 9223372036854775807;
        for i in index..value.len() as isize {
            swap(value, trouble, i, index);
            ans = get_min(ans, process1(boss, value, trouble, index + 1));
            swap(value, trouble, i, index);
        }
        return ans;
    }
}

fn swap(value: &mut Vec<isize>, trouble: &mut Vec<isize>, i: isize, j: isize) {
    let mut tmp = value[i as usize];
    value[i as usize] = value[j as usize];
    value[j as usize] = tmp;
    tmp = trouble[i as usize];
    trouble[i as usize] = trouble[j as usize];
    trouble[j as usize] = tmp;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

//  Formal approach 
//  The number of all employees is N
//  Suppose that the construction points of all employees are multiplied by M
//  Time complexity O(N * logN * logM)
fn most_min2(a: isize, _: isize, value: &mut Vec<isize>, trouble: &mut Vec<isize>) -> isize {
    let n = value.len() as isize;
    let mut l = 0;
    let mut r = 0;
    let mut value_all = a;
    let mut staff: Vec<Vec<isize>> = vec![];
    for i in 0..n {
        staff.push(vec![]);
        for _ in 0..2 {
            staff[i as usize].push(0);
        }
    }
    for i in 0..n {
        r = get_max(r, value_all / trouble[i as usize]);
        value_all *= value[i as usize];
        staff[i as usize][0] = value[i as usize] * trouble[i as usize];
        staff[i as usize][1] = value[i as usize];
    }
    staff.sort_by(|x, y| y[0].cmp(&x[0]));
    let mut m = 0;
    let mut ans = 0;
    while l <= r {
        m = l + ((r - l) >> 1);
        if yeah(value_all, &mut staff, m) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

// staff The length is N, Time complexity O(N * logN)
fn yeah(mut all: isize, staff: &mut Vec<Vec<isize>>, limit: isize) -> bool {
    let n = staff.len() as isize;
    let mut st = SegmentTree::new(n);
    let mut map: HashMap<isize, Vec<isize>> = HashMap::new();
    let mut i = 0;
    let mut index: isize = 1;
    while i < n {
        let value = staff[i as usize][1];
        st.update1(index, value);
        if !map.contains_key(&value) {
            map.insert(value, vec![]);
        }
        map.get_mut(&value).unwrap().push(index);
        i += 1;
        index += 1;
    }
    for _ in 0..n {
        let right = boundary(staff, all, limit);
        if right == 0 {
            return false;
        }
        let max = st.max1(right);
        if max == 0 {
            return false;
        }
        let mut temp = map.get_mut(&max).unwrap();
        let index = temp[0];
        temp.remove(0);
        st.update1(index, 0);
        all /= max;
    }
    return true;
}

fn boundary(staff: &mut Vec<Vec<isize>>, all: isize, limit: isize) -> isize {
    let mut l = 0;
    let mut r = staff.len() as isize - 1;
    let mut m = 0;
    let mut ans = -1;
    while l <= r {
        m = l + ((r - l) >> 1);
        if all / staff[m as usize][0] <= limit {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans + 1;
}

pub struct SegmentTree {
    pub n: isize,
    pub max: Vec<isize>,
    pub update: Vec<isize>,
}

impl SegmentTree {
    pub fn new(max_size: isize) -> Self {
        let n = max_size + 1;
        let mut max: Vec<isize> = vec![];
        let mut update: Vec<isize> = vec![];
        for _ in 0..n << 2 {
            max.push(0);
            update.push(-1);
        }
        Self { n, max, update }
    }

    pub fn update1(&mut self, index: isize, c: isize) {
        self.update0(index, index, c, 1, self.n, 1);
    }

    pub fn max1(&mut self, right: isize) -> isize {
        return self.max0(1, right, 1, self.n, 1);
    }

    fn push_up(&mut self, rt: isize) {
        self.max[rt as usize] = get_max(
            self.max[(rt << 1) as usize],
            self.max[(rt << 1 | 1) as usize],
        );
    }

    fn push_down(&mut self, rt: isize, _ln: isize, _rn: isize) {
        if self.update[rt as usize] != -1 {
            self.update[(rt << 1) as usize] = self.update[rt as usize];
            self.max[(rt << 1) as usize] = self.update[rt as usize];
            self.update[(rt << 1 | 1) as usize] = self.update[rt as usize];
            self.max[(rt << 1 | 1) as usize] = self.update[rt as usize];
            self.update[rt as usize] = -1;
        }
    }

    fn update0(&mut self, ll: isize, rr: isize, cc: isize, l: isize, r: isize, rt: isize) {
        if ll <= l && r <= rr {
            self.max[rt as usize] = cc;
            self.update[rt as usize] = cc;
            return;
        }
        let mid = (l + r) >> 1;
        self.push_down(rt, mid - l + 1, r - mid);
        if ll <= mid {
            self.update0(ll, rr, cc, l, mid, rt << 1);
        }
        if rr > mid {
            self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);
        }
        self.push_up(rt);
    }

    fn max0(&mut self, ll: isize, rr: isize, l: isize, r: isize, rt: isize) -> isize {
        if ll <= l && r <= rr {
            return self.max[rt as usize];
        }
        let mid = (l + r) >> 1;
        self.push_down(rt, mid - l + 1, r - mid);
        let mut ans = 0;
        if ll <= mid {
            ans = get_max(ans, self.max0(ll, rr, l, mid, rt << 1));
        }
        if rr > mid {
            ans = get_max(ans, self.max0(ll, rr, mid + 1, r, rt << 1 | 1));
        }
        return ans;
    }
}

//  In order to test 
fn random_array(n: isize, v: isize) -> Vec<isize> {
    let mut arr: Vec<isize> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, v) + 1);
    }
    return arr;
}

Copy

The results are as follows ：

Insert picture description here

Zuo Shen java Code