客户中心模拟（Queue and A, ACM/ICPC World Finals 2000, UVa822）rust解法
你的任务是模拟一个客户中心运作情况。客服请求一共有n（1≤n≤20）种主题，每种主题用5个整数描述：tid, num, t0, t, dt，其中tid为主题的唯一标识符，num为该主题的请求个数，t0为第一个请求的时刻，t为处理一个请求的时间，dt为相邻两个请求之间的间隔（为了简单情况，假定同一个主题的请求按照相同的间隔到达）。
客户中心有m（1≤m≤5）个客服，每个客服用至少3个整数描述：pid, k, tid1, tid2, …,
tidk ，表示一个标识符为pid的人可以处理k种主题的请求，按照优先级从大到小依次为tid1,tid2, …, tidk 。当一个人有空时，他会按照优先级顺序找到第一个可以处理的请求。如果有多个人同时选中了某个请求，上次开始处理请求的时间早的人优先；如果有并列，id小的优先。输出最后一个请求处理完毕的时刻。
分析：
每个请求项，都由其优先级最高的那个客服处理。
比如，
A客服优先级为[1 ,3, 2, 4]
B客服优先级为[2, 1, 3,]
那么请求项3，要经过两轮选择，之后由A处理。
请求项2，则只经过一轮选择，由B处理。
请求项4，要经过四轮选择，由A处理。
样例：
输入
3
128 20 0 5 10
134 25 5 6 7
153 30 10 4 5
4
10 2 128 134
11 1 134
12 2 128 153
13 1 153
15
1 68 36 23 2
2 9 6 19 60
3 67 10 6 49
4 49 44 23 66
5 81 8 18 35
6 99 85 85 75
7 94 75 94 96
8 29 7 67 28
9 100 95 11 89
10 29 16 10 29
11 32 55 10 15
12 70 48 4 84
13 100 36 63 73
14 42 93 28 47
15 100 35 2 73
3
1 13 1 2 3 4 5 6 7 8 9 11 12 13 14
2 10 2 3 4 5 9 10 11 12 14 15
3 11 1 2 3 4 5 6 7 9 13 14 15
输出
finish time 195
finish time 13899
解法：
use std::{
collections::{BTreeSet, BinaryHeap},
io,
};
#[derive(Debug)]
struct Request {
id: usize,
num: usize,
t0: usize,
t: usize,
dt: usize,
}
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
struct RequestItem {
req_id: usize,
arrive_time: usize,
process_time: usize,
}
impl Ord for RequestItem {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.arrive_time.cmp(&self.arrive_time)
}
}
impl PartialOrd for RequestItem {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
#[derive(Debug, PartialEq, Eq, Clone)]
struct Server {
id: usize,
num: usize,
req_ids: Vec<usize>,
start_process_time: usize,
finsh_process_time: usize,
}
impl Ord for Server {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
if self.finsh_process_time != other.finsh_process_time {
other.finsh_process_time.cmp(&self.finsh_process_time)
} else if self.start_process_time != other.start_process_time {
other.start_process_time.cmp(&self.start_process_time)
} else {
other.id.cmp(&self.id)
}
}
}
impl PartialOrd for Server {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
fn main() {
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
let n: usize = buf.trim().parse().unwrap();
let mut requests: Vec<Request> = vec![];
for _i in 0..n {
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
let v: Vec<usize> = buf.split_whitespace().map(|x| x.parse().unwrap()).collect();
requests.push(Request {
id: v[0],
num: v[1],
t0: v[2],
t: v[3],
dt: v[4],
});
}
//println!("{:?}", requests);
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
let m: usize = buf.trim().parse().unwrap();
let mut servers: BinaryHeap<Server> = BinaryHeap::new();
for _i in 0..m {
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
let v: Vec<usize> = buf.split_whitespace().map(|x| x.parse().unwrap()).collect();
servers.push(Server {
id: v[0],
num: v[1],
req_ids: v[2..].to_vec(),
start_process_time: 0,
finsh_process_time: 0,
});
}
//println!("{:?}", servers);
let mut request_items: BinaryHeap<RequestItem> = BinaryHeap::new();
let mut time_points: BTreeSet<usize> = BTreeSet::new();
for r in requests.iter() {
for i in 0..r.num {
let item = RequestItem {
req_id: r.id,
arrive_time: r.t0 + r.dt * i,
process_time: r.t,
};
time_points.insert(item.arrive_time);
request_items.push(item);
}
}
//println!("{:?}", request_items);
let mut finish_time = 0;
while request_items.len() > 0 {
let t = time_points.pop_first().unwrap();
//等待中的所有请求项
let mut wait_items: Vec<RequestItem> = vec![];
while let Some(i) = request_items.peek() {
if i.arrive_time <= t {
wait_items.push(*i);
request_items.pop();
} else {
break;
}
}
if wait_items.len() == 0 {
continue;
}
//所有可用的客服
let mut available_servers: Vec<Server> = vec![];
while let Some(s) = servers.peek() {
if s.finsh_process_time <= t {
available_servers.push(s.clone());
servers.pop();
} else {
break;
}
}
//请求项和客服配对，按照优先级
for i in 0..n {
if available_servers.len() == 0 || wait_items.len() == 0 {
break;
}
let mut j = 0;
while j < wait_items.len() {
let mut chosen_servers: Vec<&Server> = vec![];
//同一个请求项可能有多个客服选中
for server in available_servers.iter() {
if server.num > i && server.req_ids[i] == wait_items[j].req_id {
chosen_servers.push(server);
}
}
if chosen_servers.len() > 0 {
chosen_servers.sort_by(|a, b| {
if a.start_process_time != b.start_process_time {
a.start_process_time.cmp(&b.start_process_time)
} else {
a.id.cmp(&b.id)
}
});
//分配第一个客服给请求项，之后把客服从可用列表中删除
let mut server = chosen_servers[0].clone();
for k in 0..available_servers.len() {
if available_servers[k].id == server.id {
available_servers.remove(k);
break;
}
}
server.start_process_time = t;
server.finsh_process_time =
server.start_process_time + wait_items[j].process_time;
finish_time = finish_time.max(server.finsh_process_time);
time_points.insert(server.finsh_process_time);
servers.push(server);
wait_items.remove(j); //把请求项从等待列表中删除
} else {
j += 1;
}
}
}
if wait_items.len() > 0 {
request_items.append(&mut BinaryHeap::from(wait_items));
}
if available_servers.len() > 0 {
servers.append(&mut BinaryHeap::from(available_servers));
}
}
println!("finish time {}", finish_time);
}