数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：将数组元素相加直到所有元素都大于或等于k
我们有一个无序元素数组arr[]和一个整数K，我们需要找到使数组所有元素都大于或等于**K**所需的最小步数。我们可以将数组中的两个元素相加合并成一个元素。
示例：
Input: arr[] = {1 10 12 9 2 3},K = 6
Output: 2解释
首先我们可以将**(1 + 2)**相加，新的数组为**3 10 12 9 3**，我们可以将**(3 + 3)**相加，新的数组为**6 10 12 9**，我们可以看到列表中的所有元素都大于**6**。因此输出为
**2**，即需要**2**次操作。
示例
#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 countMinOps(int arr[], int n, int k) {
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++;
}
return res;
}
int main() {
int arr[] = {1, 10, 12, 9, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 6;
cout << countMinOps(arr, n, k);
return 0;
}输出
2
更新于：2019年10月7日
浏览量：133
广告