客户中心模拟（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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

输出

finish time 195
finish time 13899
1
2

解法：

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181