{"id":1739,"date":"2016-01-02T17:56:39","date_gmt":"2016-01-02T09:56:39","guid":{"rendered":"http:\/\/boweihe.me\/?p=1739"},"modified":"2016-01-02T17:56:39","modified_gmt":"2016-01-02T09:56:39","slug":"pat-1017-queueing-at-bank-25","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1739","title":{"rendered":"PAT 1017. Queueing at Bank (25)"},"content":{"rendered":"<p>PATEST\u94fe\u63a5\u5730\u5740\uff1a<a href=\"http:\/\/www.patest.cn\/contests\/pat-a-practise\/1017\" target=\"_blank\" rel=\"noopener noreferrer\">http:\/\/www.patest.cn\/contests\/pat-a-practise\/1017<\/a><br \/>\nSuppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his\/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.<br \/>\nNow given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.<br \/>\n\u6b64\u9898\u4e3b\u8981\u662f\u8981\u6ce8\u610f\u51e0\u4e2a\u70b9\uff1a<\/p>\n<ul>\n<li>8\u70b9\u4e4b\u524d\u5230\u7684\u987e\u5ba2\u8981\u7b498\u70b9\u5f00\u95e8<\/li>\n<li>17\u70b9\u4e4b\u540e\u5230\u7684\u987e\u5ba2\u5c31\u4e0d\u80fd\u8fdb\u5165\u4e86\uff08\u4e0d\u7b97\u5165\u5e73\u5747\u65f6\u95f4\uff09\uff0c\u4f46\u662f17\u70b9\u4e4b\u524d\u5230\u7684\uff0c\u53ef\u4ee5\u62d6\u523017\u70b9\u4e4b\u540e\u5b8c\u6210<\/li>\n<\/ul>\n<p>\u6709\u4e24\u79cd\u601d\u8def\uff0c\u4e00\u79cd\u662f\u50cf<a href=\"http:\/\/www.cnblogs.com\/Rafy\/archive\/2012\/03\/20\/2408419.html\" target=\"_blank\" rel=\"noopener noreferrer\">http:\/\/www.cnblogs.com\/Rafy\/archive\/2012\/03\/20\/2408419.html<\/a>\u4e00\u6837\u6309\u7167\u4e00\u79d2\u4e00\u79d2tick\uff0c\u8fd8\u6709\u4e00\u79cd\u662f\u6211\u7684\u601d\u8def\uff0c\u628a\u5ba2\u6237\u6309\u7167\u65f6\u95f4\u987a\u5e8f\u6392\u5e8f\uff0c\u7136\u540e\u4e00\u4e2a\u4e2a\u201c\u5582\u201d\u7ed9\u7a97\u53e3\u3002<br \/>\n\u7a97\u53e3\u53ea\u9700\u8bb0\u5f55\u5f53\u524d\u4efb\u52a1\u80fd\u5b8c\u6210\u7684\u65f6\u95f4\u70b9T1\u3002\u5ba2\u6237\u8fdb\u5165\u65f6\u95f4\u4e3aT0\u3002\u5582\u7ed9\u7a97\u53e3\u65f6\u5c31\u4e24\u4e2a\u72b6\u51b5\uff1a<\/p>\n<ol>\n<li>\u5982\u679c\u7a97\u53e3\u73b0\u5728\u6709\u5de5\u4f5c\uff0c\u90a3\u7b49\u5f85\u7684\u65f6\u95f4\u5c31\u662fT1-T0\uff1b<\/li>\n<li>\u5982\u679c\u7a97\u53e3\u73b0\u5728\u7a7a\u7f6e\uff08T1&lt;T0\uff09\uff0c\u90a3\u4e48\u7b49\u5f85\u65f6\u95f4\u4e3a0\uff1b<\/li>\n<\/ol>\n<p>\u4ee3\u7801\u5982\u4e0b<\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\nusing namespace std;\nstruct Customer\n{\n\tint comeInTime; \/\/\u5230\u8fbe\u65f6\u95f4\uff08\u79d2\uff09\n\tint processingTime; \/\/\u5904\u7406\u65f6\u95f4\uff08\u79d2\uff09\n};\nint* nextAvailableTime; \/\/\u7a97\u53e3\u7684\u4e0b\u4e2a\u53ef\u7528\u65f6\u95f4\u70b9\uff0c\u7528\u79d2\u8bb0\u5f55\nCustomer* customers;\nint N, K, N_valid;\nint compareCustomers(const void* c1, const void* c2)\n{\n\t\/\/\u65f6\u8fb0\u65e9\u7684\u6392\u5728\u524d\u9762\n\tCustomer* C1 = (Customer*)c1;\n\tCustomer* C2 = (Customer*)c2;\n\treturn C1-&gt;comeInTime - C2-&gt;comeInTime;\n}\nint getNextAvailable(Customer c)\n{\n\t\/\/\u627e\u5230\u4e0b\u4e2a\u53ef\u7528\u7a97\u53e3\uff0c\u8fd4\u56de\u7b49\u5f85\u65f6\u95f4\n\tint minTime = 100000; \/\/\u8fd9\u4e2a\u503c\u4e0d\u80fd\u662f17:00:00(61200),\u81f3\u5c11\u5f97\u662f86400\uff0c\u56e0\u4e3a\u6709\u53ef\u80fd17\u70b9\u4e4b\u524d\u6765\u7684\u987e\u5ba2\u4f1a\u7b49\u523017\u70b9\u4e4b\u540e...;\n\tint minIndex = -1;\n\tfor (int i = 0; i &lt; K; i++)\n\t{\n\t\tif (nextAvailableTime[i] &lt; minTime)\n\t\t{\n\t\t\tminTime = nextAvailableTime[i];\n\t\t\tminIndex = i;\n\t\t}\n\t}\n\tif (nextAvailableTime[minIndex] &lt; c.comeInTime)\n\t{\n\t\t\/\/\u4e4b\u524d\u5c31\u5df2\u7ecf\u7a7a\u7a97\uff1b\n\t\tnextAvailableTime[minIndex] = c.comeInTime + c.processingTime;\n\t\treturn 0;\n\t}\n\telse\n\t{\n\t\tint waitTime = nextAvailableTime[minIndex] - c.comeInTime;\n\t\tnextAvailableTime[minIndex] += c.processingTime;\n\t\treturn waitTime;\n\t}\n}\nint main()\n{\n\tscanf(\"%d %d\", &amp;N, &amp;K);\n\tcustomers = new Customer[N];\n\tnextAvailableTime = new int[K];\n\tfor (int i = 0; i &lt; K; i++)\n\t\tnextAvailableTime[i] = 8 * 3600; \/\/ 8:00:00\n\tN_valid = N;\n\tfor (int i = 0; i &lt; N_valid; i++)\n\t{\n\t\tint hh, mm, ss, procTime;\n\t\tscanf(\"%d:%d:%d %d\", &amp;hh, &amp;mm, &amp;ss, &amp;procTime);\n\t\tif (hh &gt;= 17 &amp;&amp; mm &gt;= 0 &amp;&amp; ss &gt; 0)\n\t\t{\n\t\t\tN_valid--;\n\t\t\ti--;\n\t\t\tcontinue;\n\t\t}\n\t\telse\n\t\t{\n\t\t\tcustomers[i].comeInTime = hh * 3600 + mm * 60 + ss;\n\t\t\tif (procTime &gt; 60)\n\t\t\t\tprocTime = 60;\n\t\t\tcustomers[i].processingTime = procTime * 60;\n\t\t}\n\t}\n\t\/\/\u5bf9\u6709\u6548\u987e\u5ba2\u6392\u5e8f\n\tqsort(customers, N_valid, sizeof(Customer), compareCustomers);\n\tint waitTimeSum = 0; \/\/(\u79d2)\n\tfor (int i = 0; i &lt; N_valid; i++)\n\t{\n\t\twaitTimeSum += getNextAvailable(customers[i]);\n\t}\n\tfloat waitTimeAvg = waitTimeSum \/ 60.0 \/ (float)N_valid;\n\tprintf(\"%.1f\", waitTimeAvg);\n\treturn 0;\n}\n<\/pre>\n<p>&nbsp;<br \/>\n&nbsp;<\/p>\n<table id=\"case_result_list\">\n<thead>\n<tr>\n<th class=\"header\">\u6d4b\u8bd5\u70b9<\/th>\n<th class=\"header\">\u7ed3\u679c<\/th>\n<th class=\"header\">\u7528\u65f6(ms)<\/th>\n<th class=\"header\">\u5185\u5b58(kB)<\/th>\n<th class=\"header\">\u5f97\u5206\/\u6ee1\u5206<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>0<\/td>\n<td><span class=\"caseRes-3\">\u7b54\u6848\u6b63\u786e<\/span><\/td>\n<td>1<\/td>\n<td>256<\/td>\n<td>12\/12<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td><span class=\"caseRes-3\">\u7b54\u6848\u6b63\u786e<\/span><\/td>\n<td>1<\/td>\n<td>256<\/td>\n<td>3\/3<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td><span class=\"caseRes-3\">\u7b54\u6848\u6b63\u786e<\/span><\/td>\n<td>1<\/td>\n<td>256<\/td>\n<td>3\/3<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td><span class=\"caseRes-3\">\u7b54\u6848\u6b63\u786e<\/span><\/td>\n<td>1<\/td>\n<td>368<\/td>\n<td>3\/3<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td><span class=\"caseRes-3\">\u7b54\u6848\u6b63\u786e<\/span><\/td>\n<td>1<\/td>\n<td>360<\/td>\n<td>2\/2<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td><span class=\"caseRes-3\">\u7b54\u6848\u6b63\u786e<\/span><\/td>\n<td>5<\/td>\n<td>364<\/td>\n<td>2\/2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"excerpt":{"rendered":"<p>PATEST\u94fe\u63a5\u5730\u5740\uff1ahttp:\/\/www.patest.cn\/contests\/pat-a-practise\/1017 Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his\/her turn to be served and there is a window available. It [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-1739","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1739","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1739"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1739\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1739"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1739"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1739"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}