CodeWar::DoubleCola

CodeWar上的一道题

Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on.

For example, Penny drinks the third can of cola and the queue will look like this:

Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny

Write a program that will return the name of the person who will drink the n-th cola.

这种前端删除，double后加入后面，自然想到双向队列deque来做

#include <string>
#include <vector>
#include <deque>
using namespace std;

std::string who_is_next(std::vector<std::string> names, long long r) {
  deque<string>  q;
  string tmp;
  long long i;
  for(i=0;i<names.size();i++) q.push_back(names[i]);
  for(i=1;i<r;i++)
  {
    tmp = q[0];
    q.pop_front();
    q.push_back(tmp);
    q.push_back(tmp);
  }
  return q[0];
}

简单的测试能通过，但是最终测试显示超时，果然直接操作队列太慢了，尤其给的input范围

1  ≤  n  ≤  10000000000

所以还需要找到高效的方法，
考虑整个循环，人数每轮结束后为{5，10，20，40，。。。}，除以人数5之后就是一个二进制数{1,2,4,8,...}，每一轮结束时的序号为{1,3,15,....}，因此我们只需要判断轮次。另外每一轮所处位置也可以通过右移得到

#include <string>
#include <vector>
using namespace std;

std::string who_is_next(std::vector<std::string> names, long long r) {
  r--;
  long long n = r/names.size();
  long long d;
  long long i = 64;
  while(i>0){
    i--;
    if(((n+1)&((long long)1<<i))>>i == 1) break;
  }
  d = r - (((long long)1<<i) - 1)*names.size();
  return names[d>>i];
}

提交结果后看到的优秀解答：

#include <string>
#include <vector>

std::string who_is_next(std::vector<std::string> names, long long r) {
  long long x = r;
  while (x > names.size()) {
    x = (x - names.size() + 1) / 2; 
  }
  
  return names[x-1];
}