資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中陣列的最大值，每次訪問後最大值遞減
在這個問題中，我們給定一個數組 arr[] 和一個整數 M。我們的任務是建立一個程式，在 C++ 中找到陣列中的最大值，並且每次訪問後最大值遞減。
問題描述
為了找到最大值，我們將從陣列中找到最大元素，並在每次檢索後將其減少 -1，進行 M 次。
讓我們舉個例子來理解這個問題：
輸入: arr[] = {3, 6, 8, 9} M = 2
輸出:17
解釋
第 1 次迭代，最大值 = 9，總和 = 9，更新後的陣列 = {3, 6, 8, 8}
第 2 次迭代，最大值 = 8，總和 = 9+8 = 17，更新後的陣列 = {3, 6, 7, 8}
解決方案方法
一個簡單的解決方案是使用最大堆，它將在根節點處具有最大元素。然後彈出根節點，將其減少 1，然後再次插入元素。此彈出和插入操作執行 M 次。對於每個彈出操作，我們將元素新增到 sum 元素，並在 M 次迭代後列印 sum。
示例
#include <bits/stdc++.h>
using namespace std;
int getSum(int arr[], int N, int M) {
int sumVal = 0;
priority_queue<int> heap;
for (int i = 0; i < N; i++)
heap.push(arr[i]);
while (M--) {
int maximumVal = heap.top();
sumVal += maximumVal;
heap.pop();
heap.push(maximumVal - 1);
}
return sumVal;
}
int main() {
int arr[] = { 3, 6, 8, 9};
int M = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum from array when the maximum decrements after every access is "<<getSum(arr, N,M);
}輸出
The maximum from array when the maximum decrements after every access is 17
更新於: 2020-10-09
53 次檢視
廣告