資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中，將陣列元素相加直到每個元素都大於或等於k。
陣列 − 陣列是一個包含相同資料型別元素的容器，其元素從0開始索引。
在這個問題中，我們將使用一個整數陣列。並檢查所有元素是否都大於給定數字。我們將檢查陣列的所有元素是否都大於或等於給定的數字k。如果不是，我們將新增陣列的兩個最小元素，並將此和作為單個元素處理。然後再次檢查新陣列的相同條件。如果條件為真，則返回執行求和的次數。
Array = { 2, 6,3,12, 7} K = 5
Output : 1解釋 − 首先，我們將檢查所有元素是否都大於k。由於它們不是，我們將新增兩個最小數字。分別是2和3，因此我們新陣列的第一個元素將是5。現在，我們將再次檢查，這次條件滿足，因此我們將返回我們已經完成的加法次數。
演算法
輸入 − 陣列和K
Step 1 : check if all elements are greater than or equal to K
Step 2: if(yes){
Print number of iterations.
}
exit(0)
Step 3: else {
Add smallest two elements of the array and make it one element.
}
Step 4: goto step 1示例
#include<bits/stdc++.h>
using namespace std;
class MinHeap{
int *harr;
int capacity;
int heap_size;
public:
MinHeap(int *arr, int capacity);
void heapify(int );
int parent(int i){
return (i-1)/2;
}
int left(int i){
return (2*i + 1);
}
int right(int i){
return (2*i + 2);
}
int extractMin();
int getMin(){
return harr[0];
}
int getSize(){
return heap_size;
}
void insertKey(int k);
};
MinHeap::MinHeap(int arr[], int n){
heap_size = n;
capacity = n;
harr = new int[n];
for (int i=0; i<n; i++)
harr[i] = arr[i];
for (int i=n/2-1; i>=0; i--)
heapify(i);
}
void MinHeap::insertKey(int k){
heap_size++;
int i = heap_size - 1;
harr[i] = k;
while (i != 0 && harr[parent(i)] > harr[i]){
swap(harr[i], harr[parent(i)]);
i = parent(i);
}
}
int MinHeap::extractMin(){
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1){
heap_size--;
return harr[0];
}
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
heapify(0);
return root;
}
void MinHeap::heapify(int i){
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i){
swap(harr[i], harr[smallest]);
heapify(smallest);
}
}
int main(){
int arr[] = { 2, 6,3,12, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 5;
MinHeap h(arr, n);
long int res = 0;
while (h.getMin() < k){
if (h.getSize() == 1)
return -1;
int first = h.extractMin();
int second = h.extractMin();
h.insertKey(first + second);
res++;
}
cout << res;
return 0;
}輸出
1
更新於: 2019年9月19日
166 次瀏覽
廣告