|
基本思路为模拟窗口运行，代码基本有注释。
用到了一点17的特性所以得用pta的clang++编译。稍微修改也可以用g++。
#include <iostream>
#include <iomanip>
#include <tuple>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
using namespace std;
size_t NoAvail = 0xff;
struct Window {
int served = 0; // 已服务人数
int end_serve = INT_MAX; // 完成当前任务时的时间
bool busy = 0; // 是否处于空闲状态
void work(int work_span) { //设置忙碌状态和任务完成时间
busy = true;
end_serve = work_span;
}
void complete() { //更新窗口状态函数
if (busy) {
busy = false;
this->served++;
}
}
friend ostream& operator<<(ostream& out, Window & w) { // 特化输出格式为只输出已服务人数
out << w.served ;
return out;
}
};
struct Customer {
size_t arrive_time; // 到达时间
size_t serve_time; // 服务所需时间
bool isVIP;
bool operator==(Customer& other) { // 没啥用的
if (other.arrive_time == arrive_time && other.isVIP == isVIP && other.serve_time == serve_time) return true;
else return false;
}
bool operator==(tuple<size_t, size_t, bool> ano) { // 同上
if (get<0>(ano) == arrive_time && get<1>(ano) == serve_time && get<2>(ano) == isVIP) return true;
else return false;
}
};
Window windows[13];
Customer custom[1050];
size_t vipw_idx = 0;
auto dispatch_window(size_t k) { // 分配窗口并检查分配后窗口是否全部忙碌
size_t i = 0;
bool allbusy = true; // 只在后续检查中发现有多余的窗口空闲才取false
//if (VIP) {
// if (!windows[vipw_idx].busy) i = vipw_idx;
//}
while (windows[i].busy) { // 寻找第一个空闲窗口
i++;
if (i >= k) break;
}
for (size_t j = 0; j < k; j++) { //为了后续兼容有VIP的情况索引从0开始,否则可以直接取i+1
if (j == i) continue;
if (!windows[j].busy) {
allbusy = false;
break;
}
}
return make_pair(i, allbusy); // std::pair 返回值类型由auto自动推导
}
tuple<size_t,size_t,size_t> custom_loop(size_t n,size_t k) {
size_t served = 0, w_idx, cur_time = 0, custom_idx = 0; // 总服务人数 分配到的窗口在数组中的索引 当前时间 队首顾客在数组中的索引
size_t sum_time = 0, max_time = 0, wait_cur = 0; // 总等待时间 最长等待时间 当前等待时间
bool allbusy = false;
while (served != n) { // 循环条件为服务总人数小于n
while (custom_idx < n && cur_time >= custom[custom_idx].arrive_time ) { // 只在到达时间小于等于当前时间才进行窗口分配
tie(w_idx, allbusy) = dispatch_window(k); //分配 使用cxx11::tie方便获取函数返回的pair
if (w_idx != NoAvail) { // 有空闲
windows[w_idx].work(cur_time + custom[custom_idx].serve_time); // 设置窗口状态和任务持续时间
wait_cur = cur_time - custom[custom_idx].arrive_time; // 通过到达时间和当前时间的差值来获得等待时间
if (wait_cur > max_time) max_time = wait_cur;
sum_time += wait_cur;
custom_idx++;
}
else break; // 无空闲则跳出分配过程
}
int min_time = INT_MAX;
if (allbusy) { // 若所有窗口都处于忙碌,则将时间拨到最快完成任务的窗口的结束时间,进行下一次分配
for (auto& _ : windows) {
if (_.busy && _.end_serve < min_time) min_time = _.end_serve;
}
}else if(custom_idx < n){ // 如果有空闲窗口,则将时间调至下一位顾客到达时
min_time = custom[custom_idx].arrive_time;
}
else { // 顾客仅剩下正在窗口服务的人,其余人已完成服务,直接将时间调至最后一个任务完成时
min_time = INT_MIN;
for (auto& _ : windows) {
if (_.busy && _.end_serve > min_time) min_time = _.end_serve;
}
}
for (auto& _ : windows) { // 更新调整时间后所有在这段时间内完成任务的窗口的状态,并记录服务人数
if (_.busy && _.end_serve <= min_time) {
_.complete();
served++;
allbusy = false;
}
}
cur_time = min_time; // time leap
}
return { cur_time,max_time,sum_time }; // 返回std::tuple c++元组，编译期泛型多类型容器
}
int main() {
cin.sync_with_stdio(false); // 解绑cin跟stdio，提高cin效率
cout.sync_with_stdio(false);
size_t n, tmp, k;
cin >> n;
for (size_t i = 0; i < n; i++) {
cin >> custom[i].arrive_time >> tmp;
if (tmp > 60) tmp = 60;
custom[i].serve_time = tmp;
//cin >> custom[i].isVIP;
}
cin >> k /* >> vipw_idx*/;
NoAvail = k;
auto [Time, Max, Sum] = custom_loop(n, k); // 获取模拟窗口结果，使用c++17 struct bind
// 也可以当参数引用传回来，麻烦，所以用了新特性
// iomanip setprecision 与 fixed 共用设置小数位数
// 去掉fixed则setprecision控制浮点数的整数位和小数位的总长度
cout << fixed << setprecision(1) << static_cast<double>(Sum) / n << " ";
cout << Max << " ";
cout << Time << endl;
for (size_t i = 0; i < k; i++)
{
cout << windows[i]; // 调用Window类的特化operator<< 函数输出每个窗口的服务人数
if (i != k-1) cout << " ";
}
cout << endl;
return 0;
}
|