c++ - C++ Hackerrank购买显示票证优化

  显示原文与译文双语对照的内容
79 0

几天前我在一家公司的在线筛选测试上遇到这个问题。问题语句的读取方式如下:

有n 个人排队购买 tickets.Due 高需求,场地按照以下规则销售票证:

  • 线路头的人可以以购买一张票,然后再退出。
  • 如果一个人需要购买额外的票,他们必须进入线路的末尾并等待销售他们的下一个票。
  • 每张门票只需一秒钟。

我们以 array 为代表表示初始行,票证= [ tickets0,tickets1.。ticketsN-1],ticketsi表示我希望购买的票证的数量。如果Jesse站在这条线的位置,找出他买所有票的时间。在下面的编辑器中完成等待时间函数。它有两个参数:

  • 一个 array,票据,表示排队的人的初始序列。每个ticketsi描述在初始位置等待的人的票证数量。

一个整数p,表示jesse在票证中的位置。

示例输入 5 2 6 3 4 5 2采样输出 12示例输入示例输出 11示例输出

在测试期间,我发现了通过大多数测试用例的简单方法,但在几个测试用例中得到了超时:

long waitingTime(vector<int> tickets, int p) {
//bool flag indicates whether it's Jesse or not
 queue<pair<int, bool>> aQueue;
 for(int i = 0; i <tickets.size(); i++) {
 aQueue.push(make_pair(tickets[i], i == p));
 }
 long long nTime = 1;
 while(!aQueue.empty()) {
 pair<int, bool> aItem = aQueue.front();
 aQueue.pop();
 nTime++;
 if(aItem.first == 1 && aItem.second == true)
 break;
 else if(aItem.first> 1) {
 aQueue.push(make_pair(aItem.first-1, aItem.second));
 }
 }
 return nTime-1;
}

但是,我无法找到解决这个问题的不同方法。我认为在不需要模拟整个队列流的情况下还有其他方法。如果有人能给我正确的解决这个问题的方法,我会非常感激。提前致谢!

时间:原作者:0个回答

62 1

看了两次问题后,我发现应该有一个解析的解决方案。

我的想法是:

  • 在 Jesse Jesse之前,我 Jesse Jesse min{ ticketsi,ticketsJesse } 时间。
  • Jesse自己会消耗 ticketsJesse的时间。
  • 在People的时候,我会站在杰西的前面,ticketsJesse,} 。

因此,只要简单地总结一个循环中的数字就可以了。这就意味着 O(n) 而不是 O(n2) 。

在我看来,结果也将取决于杰西的位置。但是,我的结果与示例输出有些不同。waiting-queue.cc:

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
//naive approach
int waitingTimeSim(const std::vector<int> &tickets, int p)
{
//setup sim. model
 std::queue<std::pair<int, bool>> people;
 for (int i = 0, n = (int)tickets.size(); i <n; ++i) {
 people.push(std::make_pair(tickets[i], i == p));
 }
//simulation
 int tP = 0;
 for (;;) {
 std::pair<int, bool> person = people.front();
 people.pop();
 --person.first; ++tP;//buy ticket
 if (!person.first) {//if person is done
 if (person.second) return tP;//It's Jesse -> terminate
 } else people.push(person);
 }
}
//analytical approach
int waitingTime(const std::vector<int> &tickets, int p)
{
 int tP = 0, ticketsP = tickets[p];
 for (int i = 0, n = (int)tickets.size(); i <n; ++i) {
 tP += std::min(tickets[i], ticketsP - (i> p));
//i> p -> people after jesse -> decr. by 1
 }
 return tP;
}
int main()
{
 { std::vector<int> tickets{ 2, 6, 3, 4, 5 };
 for (int p = 0, n = tickets.size(); p <n; ++p) {
 std::cout <<"tickets{ 2, 6, 3, 4, 5 }, p =" <<p <<std::endl;
 int tS = waitingTimeSim(tickets, p);
 std::cout <<"simulated t:" <<tS <<std::endl;
 int t = waitingTime(tickets, p);
 std::cout <<"computed t:" <<t <<std::endl;
 }
 }
 { std::vector<int> tickets{ 5, 5, 2, 3 };
 for (int p = 0, n = tickets.size(); p <n; ++p) {
 std::cout <<"tickets{ 5, 5, 2, 3 }, p =" <<p <<std::endl;
 int tS = waitingTimeSim(tickets, p);
 std::cout <<"simulated t:" <<tS <<std::endl;
 int t = waitingTime(tickets, p);
 std::cout <<"computed t:" <<t <<std::endl;
 }
 }
 return 0;
}

我上传的源码是 ideone.com

我的测试会话( G++,CYGWIN,Windows 10 ):

$ g++ -std=c++11 -o waiting-queue waiting-queue.cc 
$./waiting-queue.exe 
tickets{ 2, 6, 3, 4, 5 }, p = 0
simulated t: 6
computed t: 6
tickets{ 2, 6, 3, 4, 5 }, p = 1
simulated t: 20
computed t: 20
tickets{ 2, 6, 3, 4, 5 }, p = 2
simulated t: 12
computed t: 12
tickets{ 2, 6, 3, 4, 5 }, p = 3
simulated t: 16
computed t: 16
tickets{ 2, 6, 3, 4, 5 }, p = 4
simulated t: 19
computed t: 19
tickets{ 5, 5, 2, 3 }, p = 0
simulated t: 14
computed t: 14
tickets{ 5, 5, 2, 3 }, p = 1
simulated t: 15
computed t: 15
tickets{ 5, 5, 2, 3 }, p = 2
simulated t: 7
computed t: 7
tickets{ 5, 5, 2, 3 }, p = 3
simulated t: 11
computed t: 11
$

备注:

无意思地说,NAME waitingTime() 是一点点信息管理系统,因为这个指定很清楚地

找出他购买所有票需要花多少时间。

因此,我的实现计算等待时间 +,Jesse需要购买最后一张罚单。

更新:

常用德语短语表示:谁能读得清楚。( 在德语中,它听起来并不像德语那么好和方便:然而,这些算法并没有改变。

原作者:
...