- 浏览: 149986 次
- 性别:
- 来自: 内蒙古
文章分类
最新评论
-
linest:
ethi_teye 写道id可能是0开头的,你用int保存再输 ...
pat-1022 Digital Library -
ethi_teye:
id可能是0开头的,你用int保存再输出,这些0就被忽略了。
pat-1022 Digital Library -
lixuanchong:
在lz的代码上稍作修改即可:
#include<iost ...
pat-1010* Radix -
air_sky:
确实。。result=a0*base^0+a1*base^1+ ...
pat-1010* Radix -
linest:
air_sky 写道
关于“方程只有一个正整数解,就可以用二分 ...
pat-1010* Radix
银行8点至17点开 有固定窗口数
来早了要等,没窗口要等,17点后才来就无视
求平均等待时间, 被无视的不统计
注意不是17点一定关门,只要是17点前来的都要服务,即使可能超时
下面代码完全模拟秒数,先排序顾客,滤掉17点后来的
对于每一秒,检查窗口的情况
总体思路是以时间为中心
网上看到下面代码,效率要高
采用优先队列,自动维护顺序,每次取最小
总体思路以顾客为中心
每次取出最近一个顾客,最近一个窗口
如果窗口时间大于顾客时间,则意味着顾客要等
如果顾客时间大于窗口时间,说明窗口空闲,用户来了即可,不用等,此时把用户的时间赋给窗口,相当于跳过了空闲时间
来早了要等,没窗口要等,17点后才来就无视
求平均等待时间, 被无视的不统计
注意不是17点一定关门,只要是17点前来的都要服务,即使可能超时
下面代码完全模拟秒数,先排序顾客,滤掉17点后来的
对于每一秒,检查窗口的情况
总体思路是以时间为中心
#include<iostream> using namespace std; #include<string> #include<vector> #include<stdio.h> #include<algorithm> #include<queue> struct Customer { int arrive; int cost; }; int time2int(string s) { int time = 0; int loc; int base = 3600; string tmp = s; for(int i=1;i<=3;i++) { loc = tmp.find(":"); time += atoi(tmp.substr(0,loc).c_str())*base; tmp = tmp.substr(loc+1); base /= 60; } return time; } string int2time(int time) { string s; char part[3]; for(int i=1;i<=3;i++) { sprintf(part,"%02d",time%60); s = string(part) + s; time /= 60; if(i!=3) s = ":"+s; } return s; } bool compare(Customer a,Customer b) { return a.arrive < b.arrive; } // care people come too early they must wait int main() { int N;//customer int K;//window vector<Customer> wait; vector<Customer> win; vector<Customer> tmp; string time; int need; int total = 0; int available; int allcus = 0; cin>>N; cin>>K; available = K; while(N--) { Customer c; cin>>time; c.arrive = time2int(time); cin>>need; c.cost = need * 60; if(c.arrive <= 17*3600) //eliminate customer coming too late { wait.push_back(c); allcus ++; } } sort(wait.begin(),wait.end(),compare); //serving time for(int t = 8*3600; !wait.empty() ;t++) { //may off at same time for(int i = 0;i<win.size();i++) { win[i].cost --; if(win[i].cost == 0) available++; //off window else tmp.push_back(win[i]); } win = tmp; tmp.clear(); //on window while(available > 0 && wait.size() > 0 && t >= wait[0].arrive) { win.push_back(wait[0]); available --; total += t - wait[0].arrive; //wait time for served customer wait.erase(wait.begin()); } } if(allcus == 0) printf("%.1f\n",0.0); else { double avg = total/(60.0*allcus); printf("%.1f\n",avg); } }
网上看到下面代码,效率要高
采用优先队列,自动维护顺序,每次取最小
总体思路以顾客为中心
每次取出最近一个顾客,最近一个窗口
如果窗口时间大于顾客时间,则意味着顾客要等
如果顾客时间大于窗口时间,说明窗口空闲,用户来了即可,不用等,此时把用户的时间赋给窗口,相当于跳过了空闲时间
#include<iostream> #include<iomanip> #include<queue> using namespace std; struct window { int mm; int hh; int ss; bool operator<(const window& a)const { if(hh>a.hh) return true; else if(hh==a.hh&&mm>a.mm) return true; else if(hh==a.hh&&mm==a.mm&&ss>a.ss) return true; else return false; } }; struct customer { int h; int m; int s; int last; bool operator<(const customer& a)const { if(h>a.h) return true; else if(h==a.h&&m>a.m) return true; else if(h==a.h&&m==a.m&&s>a.s) return true; else return false; } }; priority_queue<window> bank; priority_queue<customer> cu; int main() { int n,k,i; cin>>n>>k; window w; for(i=0;i<k;i++) { w.ss=0; w.mm=0; w.hh=8; bank.push(w); } customer cust; for(i=0;i<n;i++) { cin>>cust.h; getchar(); cin>>cust.m; getchar(); cin>>cust.s>>cust.last; cu.push(cust); } int c=0; double total=0; while(!cu.empty()) { cust=cu.top(); cu.pop(); if(cust.h>17||(cust.h==17&&cust.m)||(cust.h==17&&!cust.m&&cust.s)) break; c++; w=bank.top(); bank.pop(); if(cust.h<w.hh||(cust.h==w.hh&&cust.m<w.mm)||(cust.h==w.hh&&cust.m==w.mm&&cust.s<w.ss)) { total+=(w.hh-cust.h)*60.0+(w.mm-cust.m)+(w.ss-cust.s)/60.0; w.mm+=cust.last; w.hh+=w.mm/60; w.mm%=60; } else //have window but the customer not come yet so no need to wait { w.ss=cust.s; w.mm=cust.m+cust.last; w.hh=cust.h+w.mm/60; w.mm%=60; } bank.push(w); } cout<<fixed<<setprecision(1)<<total/c<<endl; return 0; }
发表评论
-
pat-1016 Phone Bills
2012-02-27 00:01 3095Sample Input:10 10 10 10 10 10 ... -
pat-1018 Public Bike Management 有问题
2012-02-26 19:55 3542最后一个case还过不了 == 为什么呢 思路dfs遍历到目 ... -
pat-1021* Deepest Root
2012-02-25 00:36 2727判断图是否都连接构成树,求使树高最大的根 实际上求图上两点间 ... -
pat-1022 Digital Library
2012-02-27 14:26 1741可能的查询 ID值进行map映射 以下代码有问题,原因 ... -
pat-1020* Tree Traversals
2012-02-23 15:20 1463给后序和中序遍历 求层序遍历 Sample Input:7 ... -
pat-1019 General Palindromic Number
2012-02-23 00:26 1058判断数字在给定进制下是否回文 并打出进制转换后系数 思路,将 ... -
pat-1026 Table Tennis
2012-02-19 19:19 0题意?? 多个桌可用 vip桌可用时 队中vip还是最小号 ... -
pat-1025 PAT Ranking
2012-02-19 15:45 1312不同地点一起排序 先组内排序,再全局排序 将小组添加进全局 ... -
pat-1024 Palindromic Number
2012-02-20 00:56 1955如果不是回文则进行逆序相加操作,打印出最后回文和操作次数 题 ... -
pat-1023 Have Fun with Numbers
2012-02-19 00:26 2504判断一个数乘2后是否是原数的一个排列 思路: int最大值 ... -
pat-1015 Reversible Primes
2011-09-28 20:08 1441将数字转成指定进制,再反序,判断原数和新数是否都是质数。 ... -
pat-1009 Product of Polynomials
2011-09-19 23:31 11821009:多项式乘积。 Sample Input 2 1 2 ... -
pat-1008 Elevator
2011-09-19 23:09 8961008: 电梯上升一层6秒,下降4秒,停留5秒。给出请求序列 ... -
pat-1007 Maximum Subsequence Sum
2011-09-19 22:59 14641007:连续和最大子串。 O(n)时间即可完成,不需存储空 ... -
pat-1006 Sign In and Sign Out
2011-09-18 23:35 13941006:给出进入和离开时间,求最早来和最晚走的人 Samp ... -
pat-1005 Spell It Right
2011-09-18 22:52 10611005:计算各个数字的和,并翻译成英文。 Sample I ... -
pat-1004* Counting Leaves
2011-09-18 22:35 16811004: 统计树的每一层上叶子节点的个数 Sample I ... -
pat-1010* Radix
2011-09-17 19:36 38461010: 给出两个数,已知一个数的进制,求是否可以在某进制下 ... -
pat-1014* Waiting in Line
2011-09-17 10:42 18561014: 排队服务问题,队列实现。 注意条件控制。 # ... -
pat-1012 The Best Rank
2011-09-16 23:58 18671012: 找出最佳排名 代码有点冗余。。。用了一些stl容 ...
相关推荐
In general we do not like to wait. But reduction of the waiting time usually requires extra investments. To decide whether or not to invest, it is important to know the effect of the investment on the...
Fundamentals of queueing Networks,Hongchen, David. Yao, 经典的排队网络书籍
JPruitt-Queueing-System-archive-refs-heads-master.zip
SQS是一种简单排队系统,它使作业可以在一台或多台计算机上顺序运行。 可以检查队列,即使在运行时也可以从队列中删除作业,并且可以保留作业。 截至2011年底的最新版本是sqs-3.1。
资源来自pypi官网。 资源全名:cubicweb-queueing-0.3.0.tar.gz
Queueing Theory A Linear Algebraic Approach
Queueing System kleinrock Vol. II
作者:Leonard Kleinrock Queueing Systems Volume 1 Theory 1975 Queueing Systems Volume 2 Computer Applications 1976
Wiley::Queueing Systems, Volume 1, Theory网站上找的,共享一下。
本书教会计算机系统性能分析人员如何在他们的工作中应用排队网络模型,回答计算机系统整个生命周期中出现的成本和性能问题。
This text is written to teach the theory of Lyapunov drift ...distortion-aware data compression, energy-constrained and delay-constrained queueing, dynamic decision making for maximum profit, and more.
Some basic knowledge about queueing theory.
主要讲述排队论在数据网络中的应用,适合初学者。
The Queueing BehaviourofATMCells in OutputBuffers 97 Balance EquationsforBuffering 98 Calculating theState ProbabilityDistribution 100 Exact Analysis forFINITE OutputBuffers 104 Delays 108 End-to-end ...
计算机网络排队论基础,学习排队论的经典教材,深入浅出。
Queueing Networks and Markov Chains Modeling and Performance Evaluation with Computer Science Application第二版,排队网络的经典书籍,Gunter Bolch,Stefan Greiner, Hermann de Meer, Kishor S....
离散时间排队网络,对多种离散时间排队网络给出了乘积解形式的稳态指标的解析表达式
关于排队论的教材,包含了更新理论,排队论,以及相关的应用
非常经典的排队论的书,网上很难找到,花了好长时间才找到。