使用reduce操作的金字塔形式（先升后降）连续数组

本文概述

• C ++
• Java
• Python3

我们连续排列了N块(其中N> 2)个不同高度的石头。任务是从给定的石头阵列中制成金字塔。在金字塔中, 宝石的高度从1开始, 增加1, 直到达到某个值x, 然后减小1, 直到再次达到1, 即宝石应为1, 2, 3, 4…x – 1, x , x – 1, x – 2…1.除金字塔外的所有其他石头的高度都应为0。我们不能将任何石头从其当前位置移开, 但是, 通过支付1的费用, 我们可以减少石头的高度。我们希望将建造金字塔的成本降至最低。输出建造该金字塔的最低成本。

例子：

Input : 1 2 3 4 2 1 Output : 4 The best pyramid that can be formed in this case is: 1 2 3 2 1 0 The cost is thus: (4 - 2) + (2 - 1) + (1 - 0) = 4 Input : 1 5 2 Output : 4 We make a pyramid 1 2 1 Input : 1 2 1 Output : 0 We already have a pyramid, we do not need to do any further construction.

通过使用简单的逻辑, 我们可以证明建造成本最低的金字塔将是最大高度的金字塔。同样, 两个高度相同的庙宇的建造成本也相同。

可以显示如下：

假设将所有石头拆除到0高度的成本为x。

假设将高度为h的太阳穴拆除为高度0的成本为y。

然后, 如果有可能用给定的石头建造一个高度为h的太阳穴, 其成本将为x – y。

通过使用此方法, 我们可以将方法简化为两个主要步骤：

1.确定可以形成的最大高度的金字塔。

2.计算建造此类金字塔的成本。

假设我们知道金字塔的放置位置, 那么第二步可以以O(N)时间复杂度完成。

因此, 我们的重点应该放在降低步骤1的时间复杂度上。

天真的方法

对于数组中的每个位置, 我们可以假定金字塔从该点开始。然后, 我们发现从1开始构造最大高度的庙宇的成本, 直到不可能达到更高的高度为止, 也就是说, 假设高度为1的金字塔最大, 然后假设高度为2, 依此类推。然后从所有这些成本中选择最低成本。

该方法使用时间复杂度为O(N ^ 3)。

改进方法

对于每个位置, 假设它是太阳穴的中心。移至该点的左右, 并尝试找到寺庙的最大高度。

这可以通过将位置i处的镜腿的最大高度设置为H(i)来实现, 其中H(i)是该点上的石头的高度。然后, 我们向左移动。如果此时石材的高度小于H(i)– 1, 则我们将最大高度设置为H(i – 1)+1。这样, 我们确定每个位置的最大高度。

该方法使用时间复杂度为O(N ^ 2)。

动态规划方法

通过稍微修改上述算法, 我们可以尝试获得O(N)方法。从左侧开始, 然后向右移动, 找到可以在该位置创建的最大高度金字塔。假设该位置右侧数组的一部分是左侧的镜像。如果H(i)是位置i处石头的高度, 则maxHeight(i)= Minimum(H(i), i, maxHeight(i – 1))

可以解释如下：

最大可能的高度不能超过H(i), 因为我们只能减小石头的高度, 而不能增加。

最大可能的高度不能超过i, 因为金字塔必须从高度1开始。

最大可能的高度不能超过石头之前的最大可能高度– 1, 因为每步石头必须增加1。

我们计算从右到左的相似值。然后, 我们为每个位置取这些值中的最小值。然后, 通过确定最大值, 我们可以计算出构建金字塔的最小成本。

C ++

//Program to find minimum cost for pyramid //from given array #include <iostream> using namespace std; #define ull unsigned long long //Returns minimum cost to form a pyramid ull minPyramidCost(ull arr[], ull N) { //Store the maximum possible pyramid height ull *left = new ull[N]; ull *right = new ull[N]; //Maximum height at start is 1 left[0] = min(arr[0], (ull)1); //For each position calculate maximum height for ( int i = 1; i <N; ++i) left[i] = min(arr[i], min(left[i - 1] + 1, (ull)i + 1)); //Maximum height at end is 1 right[N - 1] = min(arr[N - 1], (ull)1); //For each position calculate maximum height for ( int i = N - 2; i>= 0; --i) right[i] = min(arr[i], min(right[i + 1] + 1, N - i)); //Find minimum possible among calculated values ull tot[N]; for ( int i = 0; i <N; ++i) tot[i] = min(right[i], left[i]); //Find maximum height of pyramid ull max_ind = 0; for ( int i = 0; i <N; ++i) if (tot[i]> tot[max_ind]) max_ind = i; //Calculate cost of this pyramid ull cost = 0; ull height = tot[max_ind]; //Calculate cost of left half for ( int x = max_ind; x>= 0; --x) { cost += arr[x] - height; if (height> 0) --height; } //Calculate cost of right half height = tot[max_ind] - 1; for ( int x = max_ind + 1; x <N; ++x) { cost += arr[x] - height; if (height> 0) --height; } return cost; } //Driver code int main() { ull arr[] = {1, 2, 3, 4, 2, 1}; ull N = sizeof (arr)/sizeof (arr[0]); cout <<minPyramidCost(arr, N); return 0; }

Java

//Java program to find minimum cost for //pyramid from given array import java.util.*; class GFG{ //Returns minimum cost to form a pyramid static int minPyramidCost( int arr[], int N) { //Store the maximum possible pyramid height int left[] = new int [N]; int right[] = new int [N]; //Maximum height at start is 1 left[ 0 ] = Math.min(arr[ 0 ], 1 ); //For each position calculate maximum height for ( int i = 1 ; i <N; ++i) left[i] = Math.min(arr[i], Math.min(left[i - 1 ] + 1 , i + 1 )); //Maximum height at end is 1 right[N - 1 ] = Math.min(arr[N - 1 ], 1 ); //For each position calculate maximum height for ( int i = N - 2 ; i>= 0 ; --i) right[i] = Math.min(arr[i], Math.min(right[i + 1 ] + 1 , N - i)); //Find minimum possible among //calculated values int tot[] = new int [N]; for ( int i = 0 ; i <N; ++i) tot[i] = Math.min(right[i], left[i]); //Find maximum height of pyramid int max_ind = 0 ; for ( int i = 0 ; i <N; ++i) if (tot[i]> tot[max_ind]) max_ind = i; //Calculate cost of this pyramid int cost = 0 ; int height = tot[max_ind]; //Calculate cost of left half for ( int x = max_ind; x>= 0 ; --x) { cost += arr[x] - height; if (height> 0 ) --height; } //Calculate cost of right half height = tot[max_ind] - 1 ; for ( int x = max_ind + 1 ; x <N; ++x) { cost += arr[x] - height; if (height> 0 ) --height; } return cost; } //Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 2 , 1 }; int N = arr.length; System.out.print(minPyramidCost(arr, N)); } } //This code is contributed by chitranayal

Python3

# Program to find minimum cost for pyramid # from given array # Returns minimum cost to form a pyramid def minPyramidCost(arr: list , N): # Store the maximum possible pyramid height left = [ 0 ] * N right = [ 0 ] * N # Maximum height at start is 1 left[ 0 ] = min (arr[ 0 ], 1 ) # For each position calculate maximum height for i in range ( 1 , N): left[i] = min (arr[i], min (left[i - 1 ] + 1 , i + 1 )) # Maximum height at end is 1 right[N - 1 ] = min (arr[N - 1 ], 1 ) # For each position calculate maximum height for i in range (N - 2 , - 1 , - 1 ): right[i] = min (arr[i], min (right[i + 1 ] + 1 , N - i)) # Find minimum possible among calculated values tot = [ 0 ] * N for i in range (N): tot[i] = min (right[i], left[i]) # Find maximum height of pyramid max_ind = 0 for i in range (N): if tot[i]> tot[max_ind]: max_ind = i # Calculate cost of this pyramid cost = 0 height = tot[max_ind] # Calculate cost of left half for x in range (max_ind, - 1 , - 1 ): cost + = arr[x] - height if height> 0 : height - = 1 # Calculate cost of right half height = tot[max_ind] - 1 for x in range (max_ind + 1 , N): cost + = arr[x] - height if height> 0 : height - = 1 return cost # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 2 , 1 ] N = len (arr) print (minPyramidCost(arr, N)) # This code is contributed by # sanjeev2552

输出如下：

4

这种方法运行时间为O(N)。