【状态机dp】【 排序 】 2809使数组和小于等于 x 的最少时间

class Solution {
  public:
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
      const int n = nums1.size();
      const int sum1 = std::accumulate(nums1.begin(), nums1.end(), 0);
      const int sum2 = std::accumulate(nums2.begin(), nums2.end(), 0);
      if (sum1 <= x) { return 0; }
      vector<int> indexs(n);
      iota(indexs.begin(), indexs.end(), 0);
      sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2) {return nums2[i1] < nums2[i2]; });
      vector<vector<int>> dp(n+1, vector<int>(n + 1,INT_MIN));//dp[i][j] 表示处理完nums的前i个数，化了j秒清0的最大值
      dp[0][0] = 0;
      for (int i = 0; i < n; i++){
        const int index = indexs[i];
        for (int j = 0; j <= n; j++) {
          if (INT_MIN == dp[i][j]) { continue; }
          dp[i + 1][j] = max(dp[i + 1][j], dp[i ][j]);//第i+1个元素不选择
          if (j < n) {//第i+1个元素选择
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + nums1[index]+nums2[index]*(j+1));
          }
        } 
      }
      for (int i = 1; i <= n; i++)
      {
        int iMax = 0;
        for (int j = 0; j <= n; j++)
        {
          iMax = max(iMax, dp[j][i]);
        }
        if (sum1 + sum2 * i - iMax <= x)
        {
          return i;
        }
      }
      return -1;
    }
  };

template<class T>
void Assert(const T& t1, const T& 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> nums1, nums2;
  int x;
  {
    Solution sln;
    nums1 = { 1, 2, 3 }, nums2 = { 1, 2, 3 }, x = 4;
    auto res = sln.minimumTime(nums1, nums2, x);
    Assert(res, 3);
  }
  
}

template<class TSave,class TRecord>
class CSingUpdateLineTree
{
public:
  CSingUpdateLineTree(int iEleSize):m_iEleSize(iEleSize), m_vSave(iEleSize*4){
  }
  void Update(int index, TRecord update) {
    Update(1, 1, m_iEleSize, index + 1, update);
  }
  void Query(int leftIndex, int leftRight) {
    Query(1, 1, m_iEleSize, leftIndex + 1, leftRight + 1);
  }
  void Init() {
    Init(1, 1, m_iEleSize);
  }
  const int m_iEleSize;
protected:
  void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
  {
    if (iSaveLeft == iSaveRight) {
      OnInit(m_vSave[iNodeNO], iSaveLeft);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    Init(iNodeNO * 2, iSaveLeft, mid);
    Init(iNodeNO * 2+1, mid+1, iSaveRight);
    OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
  }
  void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft,int iQueryRight) {
    if (( iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight )) {
      OnQuery(m_vSave[iNodeNO]);
      return;
    }
    if (iSaveLeft == iSaveRight) {//没有子节点
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (mid >= iQueryLeft) {
      Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
    }
    if( mid+1 <= iQueryRight ){
      Query(iNodeNO * 2+1, mid+1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNodeNO,int iSaveLeft,int iSaveRight,int iUpdateNO, TRecord update) {
    if (iSaveLeft == iSaveRight)
    {
      OnUpdate(m_vSave[iNodeNO], update);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iUpdateNO <= mid) {
      Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
    }
    else {
      Update(iNodeNO * 2+1, mid+1, iSaveRight, iUpdateNO, update);
    }
    OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2+1],iSaveLeft,iSaveRight);
  }
  virtual void OnInit(TSave& save,int iSave)=0;
  virtual void OnQuery(TSave& save) = 0;
  virtual void OnUpdate(TSave& save, const TRecord& update) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r,int iSaveLeft,int iSaveRight) = 0;
  vector<TSave> m_vSave;
};
template<class TSave = std::pair<int,int>, class TRecord = int >
class CMyLineTree : public CSingUpdateLineTree<TSave, TRecord>
{
public:
  CMyLineTree(const vector<int>& arr):CSingUpdateLineTree<TSave,TRecord>(arr.size()){
    m_arr = arr;
    const int iMax = *std::max_element(arr.begin(), arr.end());
    m_vIndexs.resize(iMax + 1);
    for (int i = 0; i < arr.size(); i++)
    {
      m_vIndexs[arr[i]].emplace_back(i);
    }
    CSingUpdateLineTree<TSave, TRecord>::Init();
  }
  int Query(int left, int r, int threshold)
  {
    m_vCan.clear();
    CSingUpdateLineTree<TSave, TRecord>::Query(left,r);
    auto [i1, i2] = Query(left, r, m_vCan);
    return (i2 >= threshold) ? i1 : -1;
  }
protected:
  vector<int> m_vCan;
  virtual void OnQuery(TSave& save) override
  {
    m_vCan.emplace_back(save.first);
  }
  virtual void OnUpdate(TSave& save, const TRecord& update) override
  {
    save = { update,1 };
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
  {
    vector<int> vCan = { left.first,r.first };
    par = Query(iSaveLeft - 1, iSaveRight - 1, vCan);
  }
  std::pair<int, int> Query(int left, int r, vector<int> vCan)
  {
    for (const auto& n : vCan)
    {
      if (-1 == n) {
        continue;
      }
      auto it1 = std::lower_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), left);
      auto it2 = std::upper_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), r);
      const int iCnt = it2 - it1;
      if (2 * iCnt > (r - left + 1))
      {
        return { n,iCnt };
      }
    }
    return { -1,0 };
  }
  vector<vector<int>> m_vIndexs;
  vector<int> m_arr;
  virtual void OnInit(TSave& save, int iSave) override
  {
    save = { m_arr[iSave - 1],1 };
  }
};
class MajorityChecker {
public:
  MajorityChecker(vector<int>& arr) :m_lineTree(arr) {
  }
  int query(int left, int right, int threshold) {
    return m_lineTree.Query(left, right, threshold);
  }
  CMyLineTree<> m_lineTree;
};