浙大 PAT 甲级 1017 Queueing at Bank C++

发布时间:2021-10-27 19:33:44

思路

跟1014题很像,也是一道模拟排队题。区别在于1014侧重单入口多出口的排队,默认所有人都在开始时刻开始排队,而1017题黄线前的若干条队伍每队只能容纳1人,并且考虑不同时刻的到达。


数据结构考虑一个结构体Customer代表排队的人,两个成员变量:到达时间、业务办理所需时长。用一个vector代表队列,sort函数(#include)使其按照到达时间排序即可。还有一个整型数组,下标代表窗口编号,其值代表每个窗口恢复空闲的时刻,最开始为八点,过程中为占用这个窗口的用户的到达时间加上其业务所需时长。


以上是大致思路,还有两个细节需要考虑:


17:00及以后到达的,不能加入vector,直接忽略即可。8:00以前到达的,如果把算法写的具有普遍性,那么这一点就完全不需要考虑。我的做法是,定义一个标记变量bool nowait,把客户分成经历了等待时间的,和未经历等待时间的,分别处理,这样算法就可能会简单一些。
代码

#include
#include
#include
using namespace std;

struct Customer
{
int atime;
int ptime;
};
vector lines;
int windows[100];

bool cmp(Customer a, Customer b)
{
return a.atime < b.atime;
}

int main()
{
int N, K;
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++)
{
int h, m, s, p;
scanf("%d:%d:%d%d", &h, &m, &s, &p);
Customer c;
c.atime = h * 3600 + m * 60 + s;
c.ptime = p;
if (c.atime < 17 * 3600)
{
lines.push_back(c);
}
}
for (int i = 0; i < K; i++)
{
windows[i] = 8 * 3600;
}
sort(lines.begin(), lines.end(), cmp);
float sum = 0;
for (int i = 0; i < lines.size(); i++)
{
bool nowait = false;
int min = 10000000;
int w = -1;
for (int j = 0; j < K; j++)
{
if (windows[j] < lines[i].atime)
{
windows[j] = lines[i].atime + lines[i].ptime * 60;
nowait = true;
break;
}
if (windows[j] < min)
{
min = windows[j];
w = j;
}
}
if (!nowait)
{
sum += windows[w] - lines[i].atime;
windows[w] += lines[i].ptime * 60;
}
}
printf("%.1f", sum / 60.0 / (float)lines.size());
return 0;
}

?

相关文档

  • matlab 能量法解耦,能量法解耦,Energy decoupling,音标,读音,翻译,英文例句,英语词典...
  • 葡萄酒的礼仪
  • Android O 新特性介绍:自适应图标(Adaptive Icons)
  • OSI/RM模型的编址方案与TCP/IP编址方案的对比
  • 小明借伞给小军
  • 关于带有箭字的成语有哪些
  • iftop入门 流量监控(找出服务器耗费流量最多的ip和端口)
  • 《Python游戏趣味编程》 第1章 Python与开发环境介绍
  • Java面向对象高级--抽象类的基本概念------abstract
  • 多模块springboot项目启动访问不了jsp页面
  • 【CryptoZombies - 2 Solidity 进阶】006 payable修饰符与提现
  • 接吻对人体有什么好处这七大益处你要知道
  • 从本地将文件传到docker容器
  • 安全意识为主题的黑板报
  • 一个案例网站整体改版优化
  • 地球环保公益广告词
  • 183sx是什么牌子的衣服
  • 工作简历封面
  • 云南香格里拉旅游后的心得
  • 微信里的图片保存在哪里
  • 职场礼仪常识黑板报
  • 销售顾问个人工作计划2020年范例
  • 爱跳绳的我
  • 洗鼻盐可以吃吗我今天煲汤没买盐只有几包洗鼻盐
  • 大将柴绍怎么死的
  • LOL英雄联盟怎么调节鼠标移动速度
  • 雨果的作品:船长
  • 女人贫血吃什么补血最快(2)
  • 微信无法打开xlsx文件_微信小程序 h5下载xlsx 文件
  • 2021年经典语句82句
  • 猜你喜欢

    电脑版