最小代价问题

问题描述

给定一个数组 a，每个元素的值代表当前的数字，数组中的第i个数加1的代价是 b[i]。你需要找出最小的代价，使得数组a中的所有元素都各不相同.

思路

优先队列+贪心

例如：a={1,1,1,1,1} b={1,2,3,4,5}

通过把a变为{2,2,2,2,1}->{3,3,3,2,1}->{4,4,3,2,1}->{5,4,3,2,1}

用优先队列维护相同元素加1的代价最大值，这个代价最大值对应的a[i]的不动，其他相同元素都加1，ans加上使元素不同的最小代价

代码实现

int solution(int n, std::vector<int> a, std::vector<int> b) {

  vector<pair<int, int>> arr;
  for (int i = 0; i < n; i++) {
    arr.push_back({a[i], b[i]});
  }

  //按a[i]从小到大排序
  sort(arr.begin(), arr.end());

  //优先队列维护a[i]相同下的b[i]
  priority_queue<int, vector<int>, less<int>> q;

  // sum是当前去掉相同元素的代价，tot是当前数字
  int sum = 0, tot = arr[0].first, ans = 0;
  int i = 0;
  while (!(i >= n && q.empty())) {

    //维护所有a中相同tot的优先队列
    while (i < n && arr[i].first == tot) {
      q.push(arr[i].second);
      sum += arr[i].second;
      i++;
    }

    //减去堆顶值
    if (!q.empty()) {
      sum -= q.top();
      ans += sum;
      q.pop();
    }

    //当前值加一
    tot++;
  }

  return ans;
}

（补充）优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

定义：priority_queue<Type, Container, Functional>

1 //升序队列，小顶堆
2 priority_queue <int,vector<int>,greater<int> > q;
3 //降序队列，大顶堆
4 priority_queue <int,vector<int>,less<int> >q;
5 
6 //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）


//自定义比较
auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
    return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);