2279. 装满石头的背包的最大数量

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
      // 存放每个背包还可放入物件数，相同类型的放入数只保存放入一次
      vector<int> spaceVec;
      
      // key：spaceVec中的值
      // value : 这种放入数的背包个数 
      map<int, int> map;
      
      int ans = 0;
      
      // 遍历所有背包，记录空余数
      for(int i = 0; i < capacity.size(); i++){
        // 背包大小
        int cap = capacity[i];
  
        // 背包已放入数量 
        int roc = rocks[i];
        
        if(cap > roc){
          // 背包还可放入数量
          int tmp = cap - roc;
          
          auto it = map.find(tmp);
          if(it == end(map)){
            // 没有记录过
            spaceVec.push_back(tmp);
            map.emplace(tmp, 1);
          }else{
            // 记录过只将数量加一
            map[tmp] = map[tmp] + 1;
          }
        }else if(roc == cap){
          // 背包本身已经满
          ans++;
        }
      }
      
      // 为了获取最大的满背包数量
      // 这里将 可放入数 进行递增排序
      sort(begin(spaceVec), end(spaceVec));
      
      // 可利用的物件数
      int avail = additionalRocks;
      
      // 从小到大遍历 可放入数 容器
      for(int i = 0; i < spaceVec.size(); i++){
        // 可放入数
        int roc = spaceVec[i];

        // 改数量可放入数的出现次数
        int times = map[roc];

        while(times-- > 0){
          // 当利用物件小于0是，直接返回当前结果
          if(0 > (avail -= roc)){
            return ans;
          }

          // 满足放入则累加结果
          ans++;
        }
      }
      
      return ans;
    }
};