网站建设运营工作业绩,百度 营销推广费用,手机主页网址大全,网络设计报告3000你的任务是模拟一个客户中心运作情况。客服请求一共有n#xff08;1≤n≤20#xff09;种主题#xff0c;每种主题用5个整数描述#xff1a;tid, num, t0, t, dt#xff0c;其中tid为主题的唯一标识符#xff0c;num为该主题的请求个数#xff0c;t0为第一个请求的时刻1≤n≤20种主题每种主题用5个整数描述tid, num, t0, t, dt其中tid为主题的唯一标识符num为该主题的请求个数t0为第一个请求的时刻t为处理一个请求的时间dt为相邻两个请求之间的间隔为了简单情况假定同一个主题的请求按照相同的间隔到达。 客户中心有m1≤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) - Optionstd::cmp::Ordering {Some(self.cmp(other))}
}#[derive(Debug, PartialEq, Eq, Clone)]
struct Server {id: usize,num: usize,req_ids: Vecusize,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) - Optionstd::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: VecRequest vec![];for _i in 0..n {let mut buf String::new();io::stdin().read_line(mut buf).unwrap();let v: Vecusize 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: BinaryHeapServer BinaryHeap::new();for _i in 0..m {let mut buf String::new();io::stdin().read_line(mut buf).unwrap();let v: Vecusize 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: BinaryHeapRequestItem BinaryHeap::new();let mut time_points: BTreeSetusize 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: VecRequestItem 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: VecServer 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: VecServer 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);
}
