数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中查找最多选择K对的数组对的最大成本
假设我们有一个对的数组A；我们必须找到最多选择K对的最大成本。在这种情况下，一对类型元素数组的成本是所选对的第一元素之和与所选对的第二元素中最小的元素的乘积。例如，如果选择这些对 (4, 8), (10, 3) 和 (3, 6)，则当K=3时，成本将为 (4+10+3)*(3) = 51。
因此，如果输入类似于 A = [(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18), (3, 8), (12, 17)], K = 4，则输出将为 2700。
为了解决这个问题，我们将遵循以下步骤：
res := 0, sum = 0
N := A的大小
定义一个名为my_set的对集
根据每对的第二个值对数组A进行排序
对于初始化 i := N - 1，当 i >= 0，更新 (i减1)，执行：
创建一个对 (A[i] 的第一个元素, i) 并将其插入到my_set中
sum := sum + A[i] 的第一个元素
当 my_set 的大小 > K 时，执行：
it := my_set 的第一个元素
sum := sum - it 的第一个元素
从my_set中删除it
res := res 和 sum * A[i] 的第二个元素 的最大值
返回 res
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
bool compactor(const pair<int, int>& a,const pair<int, int>& b) {
return (a.second < b.second);
}
int get_maximum_cost(vector<pair<int, int> > &A, int K){
int res = 0, sum = 0;
int N = A.size();
set<pair<int, int>> 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<pair<int, int> > 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输出
2700
更新于：2020年8月20日
164 次查看
广告