当前位置：首页 > 编程日记 > 正文

PAT甲级排队问题合集 (持续更新中)

编程日记 2024-09-06 08:20:00

已加入的习题

A1014,A1017

问题1和2共性

1. 都是排队问题

2. 都有一条黄线

3. 都需要找到最先离开人的队伍

4. 都有着服务时间段限制(迟于某个时间点来不予受理)

问题1：1014 Waiting in Line

问题链接：1014 Waiting in Line

这一题，所有的顾客一起来了，但是有个先后顺序。不会出现哪条队伍在某段时间没有处理任何事务的情况。

考虑到队伍有着先进先出的特点，所以用queue<int>来模拟。

最后要求出给定编号的顾客被处理结束的时间点。该问题可以转化为求给定编号的顾客问题得到处理的总时长，包括等待时间+自身被处理时间。分别存放在数组wt和pt中，其中pt直接读入，wt则需要在确定顾客所在队伍的编号，wt等于所在队伍该顾客前所有顾客的处理时间之和。这里采用一个单独的数组winTime[]，存放每个队伍已经入队的顾客处理时间之和。

现在重点解决确定每个顾客入哪个队的问题。分两种情况讨论。

1.顾客一来就可以进入黄线内。也就是编号在1~窗口数x每条队伍黄线内最多人数范围内的顾客。

他们的编号很好确定，直接用顾客编号对窗口数取余。

2.顾客并非一来就可以进入黄线内，而是要等到某一支队伍离开一个人。

问题转化为找到最先离开人的队伍。

引入数组leftTime存放每个窗口已经离开的顾客的处理时间之和，如果一支队伍的leftTime和队伍第一人的处理时间之和最小，那它就是我要找的。

易错点：

对于这句话的理解：Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output Sorry instead.

到底什么样的人对他说抱歉？不是17:00之前还没能处理完的人，而是，在17:00之前没能来的人，17:00卡点来也要说抱歉啦。

问题2：1017 Queueing at Bank

问题链接：1017 Queueing at Bank

这题所有顾客并不是一起来的，而是有着明确的抵达时间点，我们可以想象一种秒数时间制，把当天的00:00:00记为0，则开门时间和关门时间分别为

const int earliest = 8*60*60;
const int latest = 17*60*60;

和上一题相同，都是17点后（包括17点）来的人，不予受理，但是，如果一个人在十七点来，哪怕最短的队伍还要处理到17点半，这个人也会在17点半后被接着处理，可以理解成17点后，大门紧闭，但是已经进去的人加班也会被处理完。

本题要求，所有会被处理的人的等待时间的平均值，问题转化为求等待时间的总值，包括两部分：所有人等银行开门的时间+等前面的人被处理完的时间。

本题由于不是无缝对接（可能存在某个时间段某个队伍没有处理任何顾客）所有不再记录每条队伍中顾客被处理的总时间，而是能够处理下一个顾客的最早时间点。我是用数组win。win在一开始被初始化为8点的秒数时间制，每当有新的顾客加入队伍就更新一次。

用一个结构体cst来存放顾客的信息：

struct cst{int trueArrSec = 0;//真实的秒数制抵达时间（用于排序） int arrSec = 0;//(矫正后)秒数制的抵达时间 int pm = 0;//process minute 事件处理的分钟数 
};

一开始我是没有trueArrSec这个属性的，直到发现需要使用这个属性来排序。。。

用结构体数组来存放待处理顾客队列

vector<cst> vi;//待处理顾客队列

根据到达时间点对顾客排序，然后每个顾客都判断当前哪支队伍先离开人。

在这个过程中，1是要更新队伍能处理下一个顾客的时间点，2是要增加等待时间的总值，也就是出现顾客抵达的时间点小于当前队伍能处理下一个顾客的时间点，要把这个时间差加上。

tws += max(0,wSec-vi[i].arrSec);//类型2 
win[wNo] = max(vi[i].arrSec,win[wNo]) + 60*vi[i].pm;//更新当前窗口需要等待到多少秒

易错点：开始我有一个测试点是答案错误的，后来找到原因，原来在寻找最先离开人的队伍时，我把最早要等待到的时间点初始化的值不够大，后来改成10的9次方，那个用例就通过了。

问题1 AC代码

#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>using namespace std;const int sorryTime = 9*60;void print(int wt,int pt){if(wt==-1){printf("Sorry\n");return;}int totalTime = wt+pt;int h = totalTime/60;int m = totalTime%60;printf("%02d:%02d\n",8+h,m);return;
}int pt[1001] = {0};//每个顾客的处理时间processing time,顾客编号从1开始 
int wt[1001] = {0};//每个顾客的等待时间waiting time,顾客编号从1开始 int main(){int winN;//窗口数量 1<=winN<=20int capacity;//黄线内容量 1<=capacity<=10int cusN;//顾客数量 1<=cusN<=1000int QN;//查询的数量scanf("%d %d %d %d",&winN,&capacity,&cusN,&QN);for(int i=1;i<=cusN;i++){scanf("%d",&pt[i]);}queue<int> win[20];//0号到20号窗口int winTime[20] = {0};//每个窗口的总处理时间 //对于黄线内放得下的顾客 int inside = winN*capacity;//黄线内的容量 for(int i=1;i<=cusN&&i<=inside;i++){int winNo = i%winN;//i号顾客将进入窗口winNo 0<=winNo<=winN-1win[winNo].push(i);//进入窗口if(winTime[winNo]>=sorryTime)wt[i] = -1;else wt[i] = winTime[winNo];winTime[winNo]+=pt[i];//当前窗口处理的总时间增加 }int leftTime[20] = {0};//每个窗口已经离开的顾客花去的时间//对于黄线外的顾客for(int i=inside+1;i<=cusN;i++){int quickNo;//最快的窗口编号int quickWt = 1000000000;//最快的等待时间:反映哪个队伍最先缩短int leaveNo;//要离开的兄弟的编号 for(int j=0;j<winN;j++){//筛选出最先缩短的队 int h = win[j].front();if(pt[h]+leftTime[j]<quickWt){quickWt = pt[h]+leftTime[j];quickNo = j;leaveNo = h;}}//第i号顾客会在窗口quickNo的当前第一个顾客离开后加入队尾win[quickNo].pop();//当前窗口第一个顾客离队leftTime[quickNo] += pt[leaveNo];//当前窗口离开的顾客花去的时间增加if(winTime[quickNo]>=sorryTime)wt[i] = -1;else wt[i] = winTime[quickNo];win[quickNo].push(i);//顾客i入队 winTime[quickNo]+=pt[i];//当前窗口处理的总时间增加 } int no;for(int i=0;i<QN;i++){scanf("%d",&no);print(wt[no],pt[no]);}return 0;
}

问题2 AC代码

#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>using namespace std;const int maxn = 1000000000;
const int earliest = 8*60*60;
const int latest = 17*60*60;int chaToSec(int h,int m,int s){return h*60*60+m*60+s;
}struct cst{int trueArrSec = 0;//真实的秒数制抵达时间（用于排序） int arrSec = 0;//(矫正后)秒数制的抵达时间 int pm = 0;//process minute 事件处理的分钟数 
};vector<cst> vi;//待处理顾客队列 int win[100];//窗口要排队到XX秒 bool cmp(cst a,cst b){return a.trueArrSec<b.trueArrSec;
}int main(){int winN,cusN;//窗口数量，顾客数量scanf("%d %d",&cusN,&winN);int tws = 0;//totalWaitSec 总体等待秒数 由所有待处理顾客的1.等银行开门 和 2.等待他人处理时间 组成 while(cusN--){int h,m,s,pm;scanf("%d:%d:%d %d",&h,&m,&s,&pm);int arrSec = chaToSec(h,m,s);	if(arrSec<latest){//在17:00:00前来了，才会被加入待处理顾客队列 cst c;c.trueArrSec = arrSec;if(arrSec<earliest){//要是8:00前就跑来了 tws += (earliest-arrSec);//类型1 c.arrSec = earliest;}else c.arrSec = arrSec;if(pm<=60)c.pm = pm;//每个顾客被处理的时间不超过60min else c.pm = 60;vi.push_back(c);//将这个顾客加入队列 }}sort(vi.begin(),vi.end(),cmp);//将顾客按照抵达的先后顺序排序 //初始化窗口的 当前要排队到多少秒fill(win,win+winN,earliest); for(int i=0;i<vi.size();i++){int wSec = maxn;//至少等待到这一秒 int wNo = 0;//等待的窗口 for(int j=0;j<winN;j++){if(win[j]<wSec){wSec = win[j];wNo = j;}}tws += max(0,wSec-vi[i].arrSec);//类型2 win[wNo] = max(vi[i].arrSec,win[wNo]) + 60*vi[i].pm;//更新当前窗口需要等待到多少秒 } 	printf("%.1f",tws/60.0/vi.size());return 0;
}

https://www.dkcj.cn/info/17511.html

第三章：创建用户界面组件--可视化组件(一)

1.可视化组件 1.1关于可视化组件可视化组件的特征包括：size(大小）、事件、样式、皮肤、行为。行为：当组件被触发时，视觉，音乐效果的变化。 1.1 .1Spark and Halo 组件 Spark是flex 4中新加的组件。halo仍旧继承了以…

编程日记2024/09/06 08:10:00

Rust 1.30带来更多元编程支持，并改进了模块系统

Rust的最新版本1.30扩展了过程宏，允许它们定义新的属性和类似于函数的宏。此外，它简化了Rust模块系统，使其更加一致、直观。 Rust 1.30引入了两种新类型的过程宏，“类属性的过程宏”和“类函数的过程宏”。过程宏是Rust元编程的基…

编程日记2024/09/06 08:00:00

两种最大堆建堆方式

都是用完全二叉树的静态存储方式，下标从1开始。 No.1 先按照数组的次序填入完全二叉树，再从倒数第一个非叶子节点开始，一个个地看是不是要向下调整，一直下调到不能再调。 void downAdjust(int low,int high){int i low;int j …

编程日记2024/09/06 07:50:00

汉字验证码和算式验证码

大家知道简单数字或者字母验证码很容易被破解，但是算式验证码或者中文汉字验证码不容易被破解， 所以建议大家在使用验证码的时候，尽量用算式验证码或者中文汉字验证码。下面是我写的两种验证码代码，有用到的朋友可以参考下&#…

编程日记2024/09/06 07:40:00

代码 1 usingSystem;2 usingSystem.Collections.Generic;3 usingSystem.ComponentModel;4 usingSystem.Data;5 usingSystem.Drawing;6 usingSystem.Linq;7 usingSystem.Text;8 usingSystem.Windows.Forms;9 10 namespaceLinqTest11 {12 publicpartialclassForm1 : Form13 {14 p…

编程日记2024/09/06 07:30:00

Python itertools 实现全组合

>>> import itertools >>> data itertools.product([A, B], [1, 2, 3]) >>> list(data) [(A, 1), (A, 2), (A, 3), (B, 1), (B, 2), (B, 3)] 转载于:https://www.cnblogs.com/xiecl/p/9961825.html

编程日记2024/09/06 07:20:00

PAT（甲级）2021年春季考试 7-3 Structure of Max-Heap

考察：建堆，字符串的处理建堆上，跳了坑，才发现自己之前的方法过于笨拙，详情见两种最大堆建堆方式字符串处理上，走的弯路更大，但是也因此牢记了两个技巧 1. cin>>str可以用getline(cin…

编程日记2024/09/06 07:10:00

[linux内核][linux中断]——软中断机制

点击打开链接一，linux软中断的概念软中断（softirq）常常表示可延迟函数的所有种类，目前linux上使用的软中断个数是有限的，linux最多注册32个，目前使用了10个，在interrupt.h中定义，中…

编程日记2024/09/06 07:00:00

JS中8个常见的陷阱

译者按: 漫漫编程路，总有一些坑让你泪流满面。原文: Who said javascript was easy ? 译者: Fundebug为了保证可读性，本文采用意译而非直译。另外，本文版权归原作者所有，翻译仅用于学习。这里我们针对JavaScript初学者给出一些…

编程日记2024/09/06 06:50:00

支持支付宝（Alipay）付款的三个美国主机商

这段时间买国外主机的筒子们越来越多，而付款就是首先摆在大家眼前的一道障碍，大部分美国主机商只能通过信用卡购买，付款不方便。因为这个原因，很多人的美国主机都是从国内的公司或者个人买的，无法享受美国主机的优质服…

编程日记2024/09/06 06:40:00

(C++)string 的两种输入方式和输出方式

注：头文件如下 #include<string> #include<cstdio> #include<iostream>using namespace std; 注：第一种输入方式遇到回车停止读入，第二种输入方式遇到空格停止读入。两种读入方式也都可以用来读字符数组。 int main()…

编程日记2024/09/06 06:30:00

ob_get_contents();basename;file_get_contents用法

ob_get_contents(); ob_end_clean(); ob_start()使用ob_start()把输出那同输出到缓冲区，而不是到浏览器。然后用ob_get_contents得到缓冲区的数据。 ob_start()在服务器打开一个缓冲区来保存所有的输出。所以在任何时候使用echo ，输出都将被加入缓冲区中…

编程日记2024/09/06 06:20:00

零基础学汇编 --小甲鱼

来自http://www.51xue8.com/diannao/wangluobiancheng/2013-11-06/6584.html#fillback0100307b617b7b7b303232303266313839397b677b7b240000&anchortestanchor转载于:https://www.cnblogs.com/I-L-o-v-e-z-h-o-u/p/4235340.html

编程日记2024/09/06 06:10:00

数据标准化_1

from sklearn.datasets import load_irisirisload_iris()#Z-score 数据标准化from sklearn.preprocessing import StandardScalerdata_standardStandardScaler().fit_transform(iris.data)# print(data_standard,data_standard)#Min-Maxfrom sklearn.preprocessing import MinM…

编程日记2024/09/06 06:00:00

PAT甲级排队问题合集 (持续更新中)

已加入的习题

问题1和2共性

问题1：1014 Waiting in Line

问题2：1017 Queueing at Bank

问题1 AC代码

问题2 AC代码

相关文章：

第三章：创建用户界面组件--可视化组件(一)

Rust 1.30带来更多元编程支持，并改进了模块系统

两种最大堆建堆方式

汉字验证码和算式验证码

自定义Linq的Distinct

Python itertools 实现全组合

PAT（甲级）2021年春季考试 7-3 Structure of Max-Heap

[linux内核][linux中断]——软中断机制

JS中8个常见的陷阱

支持支付宝（Alipay）付款的三个美国主机商

(C++)string 的两种输入方式和输出方式

ob_get_contents();basename;file_get_contents用法

零基础学汇编 --小甲鱼

数据标准化_1

PAT（甲级）2021年春季考试 7-1 Arithmetic Progression of Primes

hadoop中HBase子项目入门讲解

C++/C union使用记一下锅

推荐60+ Flex开发参考网站

PAT（甲级）2020年秋季考试 7-4 Professional Ability Test

TestNG:org.openqa.selenium.os.UnixProcess$SeleniumWatchDog错误

项目经理修炼手册 2.1.2 项目经理的基本功

CSS3动画过渡的jquery动态弹出框插件

PAT（甲级）2021年春季考试 7-4 Recycling of Shared Bicycles

JAVA抽象类和接口的区别【附经典分析用例Door】

sql 2005提示未能加载包Microsoft SQL Management Studio Package

puppeteer爬虫的奇妙之旅

(C++)异常退出情况合集(持续更新中)

Resin介绍及其使用配置

Linux基础教程之linux文件权限深度解读

浙江大学软件学院2020年保研上机模拟练习 7-4 Shopping With Coupons