【反悔贪心】【优先队列】3049. 标记所有下标的最早秒数 II

namespace NBinarySearch
{
  template<class INDEX_TYPE, class _Pr>
  INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr)
  {
    while (rightInclue - left > 1)
    {
      const auto mid = left + (rightInclue - left) / 2;
      if (pr(mid))
      {
        rightInclue = mid;
      }
      else
      {
        left = mid;
      }
    }
    return rightInclue;
  }
  template<class INDEX_TYPE, class _Pr>
  INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr)
  {
    while (right - leftInclude > 1)
    {
      const auto mid = leftInclude + (right - leftInclude) / 2;
      if (pr(mid))
      {
        leftInclude = mid;
      }
      else
      {
        right = mid;
      }
    }
    return leftInclude;
  }
}
class Solution {
public:
  int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
    vector<bool> vCanQuick(nums.size());
    for (auto& n : changeIndices)
    {
      n--;
      if(vCanQuick[n])
      {
        n = -1;
      }
      else
      {
        vCanQuick[n] = true;
      }
    }
    auto Can = [&](int mid)
    {
      std::priority_queue<int, vector<int>, std::greater<>> minHeap;
      for (int i = mid - 1; i >= 0; i--)
      {
        const int iStudy = changeIndices[i];
        if ((-1 == iStudy) || (nums[iStudy] < 2))
        {
          continue;
        }
        if ((mid - i) / 2 > minHeap.size())
        {
          minHeap.emplace(nums[iStudy]);
        }
        else if (minHeap.size() && (minHeap.top() < nums[iStudy]))
        {
          minHeap.pop();
          minHeap.emplace(nums[iStudy]);
        }
      }
      long long llNeed = std::accumulate(nums.begin(), nums.end(), 0LL) + nums.size();//自学考试总用时
      const int iRemain = mid - minHeap.size();//可以用于考试、自学的时间
      while (minHeap.size()) {
        llNeed -= minHeap.top();
        minHeap.pop();
      }
      return iRemain >= llNeed;
    };
    int iRet =  NBinarySearch::FindFrist(-1, (int)changeIndices.size(), Can);
    return Can(iRet) ? iRet : -1;
  }
};

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()
{
  vector<int> nums, changeIndices;
  {
    Solution sln;
    nums = { 0,2,0,1 }, changeIndices = { 2,3,2,3,4,4,1,3 };
    auto res = sln.earliestSecondToMarkIndices(nums, changeIndices);
    Assert(6, res);
  }
  {
    Solution sln;
    nums = { 3, 2, 3 }, changeIndices = { 1, 3, 2, 2, 2, 2, 3 };
    auto res = sln.earliestSecondToMarkIndices(nums, changeIndices);
    Assert(6, res);
  }
  {
    Solution sln;
    nums = { 0,0,1,2 }, changeIndices = { 1,2,1,2,1,2,1,2 };
    auto res = sln.earliestSecondToMarkIndices(nums, changeIndices);
    Assert(7, res);
  }
  {
    Solution sln;
    nums = { 1,2,3 }, changeIndices = { 1,2,3 };
    auto res = sln.earliestSecondToMarkIndices(nums, changeIndices);
    Assert(-1, res);
  } 
}