2022-07-01：某公司年会上，大家要玩一食发奖金游戏，一共有n个员工， 每个员工都有建设积分和捣乱积分， 他们需要排成一队，在队伍最前面的一定是老板，老板也有建设积分和捣乱积分， 排好队后，所有员工都会获得各自的奖金， 该员工奖金 = 排在他前面所有人的建设积分乘积 / 该员工自己的捣乱积分，向下取整， 为了公平(放屁)，老板希望 : 让获得奖金最高的员工，所获得的奖金尽可能少， 所以想请你帮他重新排一下队伍，返回奖金最高的员工获得的、尽可能少的奖金数额。 快手考试的时候，给定的数据量，全排列的代码也能过的！ 1 <= n <= 1000, 1<= 积分 <= 10000; 来自阿里。
答案2022-07-01：
线段树+哈希表+二分法。
代码用rust编写。代码如下：
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;
}
执行结果如下：
京公网安备 11010502036488号