資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式中陣列最大值在每次訪問後遞減
在這個問題中，我們得到一個包含N個整數的陣列arr[]和一個整數m。我們的任務是建立一個程式來查詢陣列中的最大值，其中最大值在每次訪問後遞減。
問題描述 − 我們需要找到陣列中最大元素的最大和，並將取出的最大值減少k次。
讓我們透過一個例子來理解這個問題：
輸入
arr[] = {3, 6, 7, 8, 8}, k = 3輸出
解釋
First iteration: array before = {3, 6, 7, 8, 8}, max = 8, sum = 8, array after update = {3, 6, 7, 7, 8}
Second iteration: array before = {3, 6, 7, 7, 8}, max = 8, sum = 8 + 8 = 16, array after update = {3, 6, 7, 7, 7}
Third iteration: array before = {3, 6, 7, 7, 7}, max = 7, sum = 16 + 7 = 23, array after update = {3, 6, 6, 7, 7}
Maximum sum = 23解決方案
其思想是找到陣列的最大值，然後在新增到maxSum之後將其遞減。重複此過程k次即可得到結果。
為了找到陣列的最大元素，有多種方法，其中最有效的一種是使用最大堆資料結構。
因此，我們將把陣列的所有元素插入到最大堆中，堆中的最大元素位於其根部。我們將移除它，新增到maxSum中，並將(元素-1)重新插入到堆中。重複此過程k次即可得到所需的maxSum。
演算法
初始化 − maxSum = 0
步驟1 − 建立一個最大堆資料結構並將元素推入其中。
步驟2 − 迴圈 i -> 0 到 k 並執行步驟3-5。
步驟3 − 獲取根元素，maxVal = 根元素並將其彈出。
步驟4 − 將maxVal新增到maxSum，maxSum += maxVal
步驟5 − 將更新後的maxVal插入到最大堆中。
步驟6 − 返回maxSum。
程式演示了我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
long calcMaxSumDec(int arr[], int m, int n) {
long maxSum = 0;
long maxVal;
priority_queue<long> max_heap;
for (int i = 0; i < n; i++) {
max_heap.push(arr[i]);
}
for(int i = 0; i < m; i++) {
maxVal = max_heap.top();
maxSum += maxVal;
max_heap.pop();
max_heap.push(maxVal - 1);
}
return maxSum;
}
int main() {
int arr[] = { 2, 3, 5, 4 }, m = 3;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximums from array when the maximum decrements after every access is "<<calcMaxSumDec(arr, m, n);
}輸出
The maximums from array when the maximum decrements after every access is 13
更新於: 2020-12-22
113 次瀏覽
廣告