2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个

2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个

首页休闲益智神奇颜色球更新时间:2024-09-09

2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个,

为方便放在一个数组中,红球编号取负,篮球不变,并打乱顺序,

要求同一种颜色的球按编号升序排列,可以进行如下操作:

交换相邻两个球,求最少操作次数。

[3,-3,1,-4,2,-2,-1,4]、

最终交换结果为:

[1,2,3,-1,-2,-3,-4,4]。

最少交换次数为10,

n <= 1000。

答案2023-02-16:

动态规划,IndexTree。

代码用rust编写。代码如下:

use std::collections::HashMap; use std::iter::repeat; fn main() { let mut arr = vec![3, -3, 1, -4, 2, -2, -1, 4]; println!("{}", min_swaps(&mut arr)); } // [3,-3,1,-4,2,-2,-1,4] // -3 -4 -2 -1 -> -1 -2 -3 -4 // 3 1 2 4 -> 1 2 3 4 // 这个题写对数器太麻烦了 // 所以这就是正式解 fn min_swaps(arr: &mut Vec<i32>) -> i32 { let n = arr.len() as i32; let mut map: HashMap<i32, i32> = HashMap::new(); let mut top_a = 0; let mut top_b = 0; for i in 0..n { if arr[i as usize] > 0 { top_a = get_max(top_a, arr[i as usize]); } else { top_b = get_max(top_b, abs(arr[i as usize])); } map.insert(arr[i as usize], i); } let mut it = IndexTree::new(n); for i in 0..n { it.add(i, 1); } return f(top_a, top_b, &mut it, n - 1, &mut map); } // 可以改二维动态规划! // 因为it的状态,只由topA和topB决定 // 所以it的状态不用作为可变参数! fn f(top_a: i32, top_b: i32, it: &mut IndexTree, end: i32, map: &mut HashMap<i32, i32>) -> i32 { if top_a == 0 && top_b == 0 { return 0; } let mut p1 = i32::MAX; let mut p2 = i32::MAX; let mut index: i32; let mut cost: i32; let mut next: i32; if top_a != 0 { index = *map.get(&top_a).unwrap(); cost = it.sum(index, end) - 1; it.add(index, -1); next = f(top_a - 1, top_b, it, end, map); it.add(index, 1); p1 = cost next; } if top_b != 0 { index = *map.get(&(-top_b)).unwrap(); cost = it.sum(index, end) - 1; it.add(index, -1); next = f(top_a, top_b - 1, it, end, map); it.add(index, 1); p2 = cost next; } return get_min(p1, p2); } 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 } } fn abs(a: i32) -> i32 { if a < 0 { -a } else { a } } struct IndexTree { tree: Vec<i32>, nn: i32, } impl IndexTree { pub fn new(size: i32) -> Self { Self { tree: repeat(0).take((size 1) as usize).collect(), nn: size, } } pub fn add(&mut self, mut i: i32, v: i32) { i = 1; while i <= self.nn { self.tree[i as usize] = v; i = i & -i; } } pub fn sum(&mut self, l: i32, r: i32) -> i32 { return if l == 0 { self.sum0(r 1) } else { self.sum0(r 1) - self.sum0(l) }; } fn sum0(&mut self, mut index: i32) -> i32 { let mut ans = 0; while index > 0 { ans = self.tree[index as usize]; index -= index & -index; } return ans; } }

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved