資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告