2022-12-20:二狗买了一些小兵玩具,和大胖一起玩,一共有n个小兵,这n个小兵拍成一列,第i个小兵战斗力为hi,然后他们两
2023-02-26 09:49:34 时间
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩,
一共有n个小兵,这n个小兵拍成一列,
第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列,
一共进行m次操作,二狗每次操作选择一个数k,将前k个小兵战斗力从小到大排列,
大胖每次操作选择一个数k,将前k个小兵战斗力从大到小排列,
问所有操作结束后,排列顺序什么样,
给定一个长度为n的数组arr,表示每个小兵的战斗力,
给定一个长度为m的数组op,
op[i] = { k , 0 }, 表示对前k个士兵执行从小到大的操作,
op[i] = { k , 1 }, 表示对前k个士兵执行从大到小的操作。
返回数组ans,表示最终的排列。
1 <= n, m <= 2 * 10^5,
-10 ^ 9<= arr[i] <= + 10^9。
来自百度。
答案2022-12-20:
单调栈+有序表。
rust语言里结构体的有序表需要实现Ord的trait。
时间复杂度O(M) + O(N*logN)。
rust代码如下:
use rand::Rng;
use std::cmp::Ordering;
use std::collections::BTreeSet;
use std::iter::repeat;
fn main() {
let mut arr = vec![3, 2, 6, 7, 5, 1];
let mut op = vec![vec![3, 0], vec![4, 1], vec![2, 0]];
let ans2 = game2(&mut arr, &mut op);
println!("ans2 = {:?}", ans2);
let nn: i32 = 200;
let mm: i32 = 100;
let vv: i32 = 200;
let test_time: i32 = 5000;
println!("测试开始");
for i in 0..test_time {
let n: i32 = rand::thread_rng().gen_range(0, nn) + 1;
let m: i32 = rand::thread_rng().gen_range(0, mm) + 1;
let mut arr = random_array(n, vv);
let mut op = random_op(m, n);
let ans1 = game1(&mut arr, &mut op);
let ans2 = game2(&mut arr, &mut op);
if ans1 != ans2 {
println!("出错了!");
println!("i = {}", i);
println!("ans1 = {:?}", ans1);
println!("ans2 = {:?}", ans2);
break;
}
}
println!("测试结束");
}
// 暴力方法
// 为了验证
fn game1(arr: &mut Vec<i32>, op: &mut Vec<Vec<i32>>) -> Vec<i32> {
let n = arr.len() as i32;
let mut help: Vec<i32> = repeat(0).take(n as usize).collect();
for i in 0..n {
help[i as usize] = arr[i as usize];
}
for o in op.iter() {
if o[1] == 0 {
help[0..o[0] as usize].sort_by(|a, b| a.cmp(b));
} else {
help[0..o[0] as usize].sort_by(|a, b| b.cmp(a));
}
}
let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();
for i in 0..n {
ans[i as usize] = help[i as usize];
}
return ans;
}
// 正式方法
// 时间复杂度O(M) + O(N*logN)
fn game2(arr: &mut Vec<i32>, op: &mut Vec<Vec<i32>>) -> Vec<i32> {
let n = arr.len() as i32;
let m = op.len() as i32;
let mut stack: Vec<i32> = repeat(0).take(m as usize).collect();
let mut r = 0;
for i in 0..m {
while r != 0 && op[stack[(r - 1) as usize] as usize][0] <= op[i as usize][0] {
r -= 1;
}
stack[r as usize] = i;
r += 1;
}
let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();
let mut ansi = n - 1;
let mut l = 0;
while ansi >= op[stack[l as usize] as usize][0] {
ans[ansi as usize] = arr[ansi as usize];
ansi -= 1;
}
let mut sorted: BTreeSet<Number> = BTreeSet::new();
for i in 0..op[stack[l as usize] as usize][0] {
sorted.insert(Number::new(arr[i as usize], i));
}
while l != r {
// 当前处理的指令
let cur = &op[stack[l as usize] as usize];
l += 1;
if l != r {
let mut next = &op[stack[l as usize] as usize];
let num = cur[0] - next[0];
if cur[1] == 0 {
for i in 0..num {
ans[ansi as usize] = sorted.pop_last().unwrap().value;
ansi -= 1;
}
} else {
for i in 0..num {
ans[ansi as usize] = sorted.pop_first().unwrap().value;
ansi -= 1;
}
}
} else {
if cur[1] == 0 {
while sorted.len() > 0 {
ans[ansi as usize] = sorted.pop_last().unwrap().value;
ansi -= 1;
}
} else {
while sorted.len() > 0 {
ans[ansi as usize] = sorted.pop_first().unwrap().value;
ansi -= 1;
}
}
}
}
return ans;
}
struct Number {
value: i32,
index: i32,
}
impl Number {
fn new(v: i32, i: i32) -> Self {
Self { value: v, index: i }
}
}
impl Ord for Number {
fn cmp(&self, other: &Self) -> Ordering {
if self.value != other.value {
self.value.cmp(&other.value)
} else {
self.index.cmp(&other.index)
}
}
}
impl PartialOrd for Number {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for Number {
fn eq(&self, other: &Self) -> bool {
(self.value, &self.index) == (other.value, &other.index)
}
}
impl Eq for Number {}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();
for i in 0..n {
ans[i as usize] = rand::thread_rng().gen_range(0, v) + 1;
}
return ans;
}
// 为了测试
fn random_op(m: i32, n: i32) -> Vec<Vec<i32>> {
let mut ans: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())
.take(m as usize)
.collect();
for i in 0..m {
ans[i as usize][0] = rand::thread_rng().gen_range(0, n + 1);
ans[i as usize][1] = rand::thread_rng().gen_range(0, 2);
}
return ans;
}
// 为了测试
fn is_equal(arr1: &mut Vec<i32>, arr2: &mut Vec<i32>) -> bool {
if arr1.len() != arr2.len() {
return false;
}
for i in 0..arr1.len() {
if arr1[i as usize] != arr2[i as usize] {
return false;
}
}
return true;
}
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023