「力扣挑战赛」有 n 个比赛场馆（场馆编号从 0 开始），场馆之间的通道分布情况记录于二维数组 edges 中，edges[i]= [x, y] 表示第 i 条通道连接场馆 x 和场馆 y(即两个场馆相邻)。初始每个场馆中都有一定人数的志愿者（不同场馆人数可能不同），后续 m 天每天均会根据赛事热度进行志愿者人数调配。调配方案分为如下三种：
impl Solution {
pub fn volunteer_deployment(final_cnt: Vec<i32>, total_num: i64, mut edges: Vec<Vec<i32>>, mut plans: Vec<Vec<i32>>) -> Vec<i32> {
use std::collections::BTreeMap;
//需要解决的未知数
let mut to_solve: Vec<[i64;2]> = vec![];
to_solve.push([0, 1]);
for i in 0..final_cnt.len() {
to_solve.push([final_cnt[i] as i64, 0]);
}
//记录每个点与哪些点相连
let mut edges_map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for edge in edges {
let this = edge[0] as usize;
let other = edge[1] as usize;
if let Some(e) = edges_map.get_mut(&this) {
e.push(other);
}
else {
edges_map.insert(this, vec![other]);
}
if let Some(e) = edges_map.get_mut(&other) {
e.push(this);
}
else {
edges_map.insert(other, vec![this]);
}
}
// println!("BTreeMap: {:?}", edges_map);
//逆向推导
for plan in plans.into_iter().rev() {
let num = plan[0] as u32;
let idx = plan[1] as usize;
if num == 1 {
to_solve[idx][0] *= 2;
to_solve[idx][1] *= 2;
}
else {
let add_or_sub = (-1i64).pow(num+1);
let known = to_solve[idx][0];
let unknown = to_solve[idx][1];
if let Some(others) = edges_map.get(&idx) {
for other in others {
to_solve[*other][0] += add_or_sub * known;
to_solve[*other][1] += add_or_sub * unknown;
}
}
}
// println!("{:?}", plan);
// println!("{:?}\n", to_solve);
}
//求值
let mut left = 0;
let mut coefficient = 0;
for [l, c] in to_solve.iter() {
left += l;
coefficient += c;
}
let x: i32 = ((total_num - left) / coefficient) as i32;
to_solve.into_iter().map(|[a, b]| a as i32 + (b as i32)*x).collect::<Vec<i32>>()
}
}
func volunteerDeployment(finalCnt []int, totalNum int64, edges [][]int, plans [][]int) []int {
n := len(finalCnt) + 1
g := make([][]int, n)
for _, e := range edges {
u := e[0]
v := e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
m := len(plans)
tmp := make([][2]int, n)
tmp[0] = [2]int{1, 0}
for i, f := range finalCnt {
tmp[i+1][1] = f
}
for i := m - 1; i >= 0; i-- {
num := plans[i][0]
idx := plans[i][1]
if num == 1 {
tmp[idx][0] *= 2
tmp[idx][1] *= 2
} else if num == 2 {
for _, v := range g[idx] {
tmp[v][0] -= tmp[idx][0]
tmp[v][1] -= tmp[idx][1]
}
} else {
for _, v := range g[idx] {
tmp[v][0] += tmp[idx][0]
tmp[v][1] += tmp[idx][1]
}
}
}
var sum0, sum1 int
for _, t := range tmp {
sum0 += t[0]
sum1 += t[1]
}
res := make([]int, n)
x := int((totalNum - int64(sum1)) / int64(sum0))
var sum int
for i := 1; i < n; i++ {
res[i] = tmp[i][0]*x + tmp[i][1]
sum += res[i]
}
res[0] = int(totalNum - int64(sum))
return res
}
class Solution:
def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:
dc, finalCnt = defaultdict(list), [1j] + finalCnt
for i,j in edges:
dc[i].append(j)
dc[j].append(i)
for i,j in plans[::-1]:
v = finalCnt[j]
if i==1: finalCnt[j] *= 2
elif i==2:
for k in dc[j]: finalCnt[k] -= v
else:
for k in dc[j]: finalCnt[k] += v
sm = sum(finalCnt)
i = ((totalNum - sm.real) // sm.imag) if sm.imag else 0
return [int(x.real + x.imag * i) for x in finalCnt]
输入：
{:height=200}