使用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) = 4Input: 1 5 2 Output : 4 We make a pyramid 1 2 1Input: 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 - = 1return 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

输出如下：