c – Hackerrank购买演出门票优化

我的想法是：

>杰西之前的人们会留在他面前min {ticketsi,ticketsJesse}次.
>杰西自己将消耗门票杰西时代.
> Jesse之后的人将留在Jesse min {ticketi,ticketsJesse – 1}次面前.

因此,应该可以简单地在一个循环中总结数字.
这将意味着O(n)而不是O(n2).

我意识到,结果也取决于杰西的位置.
但是,我的结果看起来与样本输出有所不同.
因此,我也实施了一个天真的解决方案(类似于OP).
source 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,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,3 },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,p = 0
simulated t: 6
computed t:  6
tickets{ 2,p = 1
simulated t: 20
computed t:  20
tickets{ 2,p = 2
simulated t: 12
computed t:  12
tickets{ 2,p = 3
simulated t: 16
computed t:  16
tickets{ 2,p = 4
simulated t: 19
computed t:  19
tickets{ 5,p = 0
simulated t: 14
computed t:  14
tickets{ 5,p = 1
simulated t: 15
computed t:  15
tickets{ 5,p = 2
simulated t: 7
computed t:  7
tickets{ 5,p = 3
simulated t: 11
computed t:  11

$

注意：

恕我直言,waitTime()的名称有点误导,因为作业明确表示你必须这样做

find out how much time it would take for him to buy all tickets.

因此,我的实施计算了杰西需要购买他的最后一张票的等待时间.

更新：

一个经常使用的德语短语说：谁能读懂显然是有利的. (这听起来不像德语那么好用,也很方便：“Wer lesen kann,ist klar im Vorteil.”)然而,在再次阅读Rohan Kumar的评论答案后,我调整了我的评论输入到了OP,然后突然得到了预期的输出.但是,算法没有改变.