c++ - Hackerrank购买演出门票优化

我几天前在一家公司的在线筛选测试中遇到了这个问题。问题说明如下:



在测试期间，我想出了一种简单的方法，该方法通过了大多数测试用例，但在一些测试用例上却超时了:

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;
}

但我无法找到其他方法来解决此问题。我认为还有其他方法无需模拟整个队列流。如果有人能为我提供解决此问题的正确方法，我将不胜感激。提前致谢!

最佳答案

两次研究问题，我想到了一个解析解决方案应该是可能的。

我的想法是:

杰西之前的人i将在他面前停留min {ticketsi，ticketsJesse}次。

杰西本人将消耗门票杰西时间。

杰西之后的人i将停留在杰西min {ticketsi，ticketsJesse-1}次前面。

因此，应该有可能在一个循环中简单地将数字相加。
这将意味着O(n)而不是O(n2)。

如我所知，结果还取决于杰西的位置。
但是，我的结果看起来与示例输出有所不同。
因此，我也实现了一个简单的解决方案(类似于OP)。
源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。

我的测试 session (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

$

笔记:

恕我直言，名字waitingTime()有点误导，因为作业清楚地表明您必须



因此，我的实现计算的是Jesse购买最后一张机票所需的等待时间 + 。

更新:

一个常用的德语短语说:谁会读显然是有好处的。 (听起来不像德语的英语好听和方便:“Wer lesen kann，ist klar im Vorteil。”)但是，在再次阅读了Rohan Kumar的评论答案后，我调整了示例输入到OP，突然得到了预期的输出。但是，算法没有改变。

关于c++ - Hackerrank购买演出门票优化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43950000/