客户中心模拟（Queue and A, ACM/ICPC World Finals 2000, UVa822）rust解法

解法"/>

客户中心模拟（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 15315
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);
}