2022-07-01：某公司年会上，大家要玩一食发奖金游戏，一共有n个员工， 每个员工都有建设积分和捣乱积分， 他们需要排成一队，在队伍最前面的一定是老板

use rand::Rng;
use std::collections::HashMap;
fn main() {
    let n: isize = 9;
    let v: isize = 50;
    let test_time: i32 = 5000;
    println!("测试开始");
    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!("出错了!{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

// 暴力方法
// 为了验证
// a : 老板的贡献积分
// b : 老板的捣乱积分
// value[i] : i号员工的贡献积分
// trouble[i] : i号员工的捣乱积分
// 返回 : 奖金最高的员工获得的、尽可能少的奖金数额
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
    }
}

// 正式方法
// 所有员工数量为N
// 假设所有员工建设积分乘起来为M
// 时间复杂度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长度为N，时间复杂度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;
    }
}

// 为了测试
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;
}