好资源导航 » 文章资讯 » 找到在 C++ 中最多选择 K 对的一组对的最大成本

找到在 C++ 中最多选择 K 对的一组对的最大成本

2023-06-21 15:41:03 74

假设我们有一个由对A组成的数组；我们必须找到最多选择K对的最大成本。在这种情况下，pair类型元素数组的成本是所选对的第一个元素与所选对的第二个元素中最小的元素之和的乘积。例如，如果选择这些对(4,8)、(10,3)和(3,6)，那么成本将为(4+10+3)*(3)=51，对于K=3

所以，如果输入像A=[(15,5),(65,25),(35,20),(20,5),(35,20),(15,18),(3,8),(12,17)],K=4,那么输出将是2700

在线示例

让我们看看以下实现以获得更好的理解-

#include 
using namespace std;
bool compactor(const pair& a,const pair& b) {
   return (a.second < b.second);
}
int get_maximum_cost(vector > &A, int K){
   int res = 0, sum = 0;
   int N = A.size();
   set> my_set;
   sort(A.begin(), A.end(), compactor);
   for (int i = N - 1; i >= 0; --i) {
      my_set.insert(make_pair(A[i].first, i));
      sum += A[i].first;
      while (my_set.size() > K) {
         auto it = my_set.begin();
         sum -= it->first;
         my_set.erase(it);
      }
      res = max(res, sum * A[i].second);
   }
   return res;
}
int main() {
   vector > arr = {{ 15, 5}, { 65, 25}, { 35, 20}, { 20, 5}, { 35, 20}, { 15, 18}, { 3, 8 }, {12, 17}};
   int K = 4;
   cout << get_maximum_cost(arr, K);
}

输入

{{15, 5},{65, 25}, { 35, 20}, { 20, 5}, { 35, 20}, { 15, 18}, { 3, 8
}, {12, 17}}, 4

输出结果

返回顶部
514930285
czq8825@qq.com

找到在 C++ 中最多选择 K 对的一组对的最大成本

在线示例

输入

热门推荐

随机推荐