【广度优先搜索】【分类讨论】900. 最佳运动员的比拼回合

class Solution {
public:
  vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
    set<pair<int, int>> pre = { {firstPlayer-1, secondPlayer-1 } };
    vector<int> vRet = { 0,0 };
    for (int step = 1; pre.size(); step++)
    {     
      set<pair<int, int>> dp;
      int nNew = n - n / 2;
      for (auto [fir, sec] : pre)
      {       
        bool bDiff = (fir < nNew) ^ (sec < nNew);//是否一个在左边，一个在右边
# define NO(a)  ( min(a,n-1-a))
        const int i1 = min(NO(fir), NO(sec));
        const int i2 = max(NO(fir), NO(sec));
        if (i1 == i2)
        {
          if (0 == vRet[0])
          {
            vRet[0] = step;
          }
          vRet[1] = step;
          continue;
        }
        const int mid = i2 - i1 - 1;
        for (int i = 0; i <= i1; i++)
        {//枚举 fir 左边队员 赢的次数
          for (int j = 0; j <= mid; j++)
          {// 枚举 fir和 sec的竞争对手 之间队员赢的数量 
            if (bDiff)
            {
              dp.emplace(nNew-i-1, j + (i1-i));
            }
            else
            {
              dp.emplace(i, i+1+j);
            }
          }
        }
      }
      pre.swap(dp);
      swap(n,nNew);
    }
    return vRet;
  }
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  int n = 11, firstPlayer = 2, secondPlayer = 4;
  {
    n = 5, firstPlayer = 1, secondPlayer = 4;
    auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
    Assert({ 2,2 }, res);
  }
  {
    n = 11, firstPlayer = 2, secondPlayer = 4;
    auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
    Assert({ 3,4 }, res);
  } 
  {
    n = 5, firstPlayer = 1, secondPlayer = 5;
    auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
    Assert({ 1,1 }, res);
  }
  {
    n = 27, firstPlayer = 12, secondPlayer = 13;
    auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
    Assert({ 2,5 }, res);
  }
  
}