在给定约束的最小移动中将数组减少到0

Question

你可以做两个动作中的一个：

1.从x=L到x=R做一个水平切割，将建筑物的高度从x=L到x=R降低1。

2.在x=P处作垂直切割，完全摧毁x=P处的建筑物，从而使其高度为零

1≤n≤1000 0≤hi≤1000

采样输入0

2

我想不出解决这个问题的方法。我的代码对以下输入不起作用：1 1 1 2 4 5 7 7 8 9**在我的代码中，我减少了所有元素的最小值。然后找出零点之间的子数组，然后比较子数组长度（j-i）与最小值。如果长度较小，那么我们需要遵循移动2，否则移动1。我的代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.Scanner;

public class Main {
    static int findmin(int arr[], int i, int j) {
        int min = Integer.MAX_VALUE;

        for (int k = i; k < j; k++) {
            if (min > arr[k]) {
                min = arr[k];
            }
        }

        return min;
    }
    static void subtractmin(int arr[], int i, int j, int min) {
        //if both the length of subarray and min are equal, we destroy separately
        if (j - i <= min) {
            for (int k = i; k < j; k++) {
                // if

                arr[k] = 0;

            }

        } else {
            //subtract all
            for (int k = i; k < j; k++)

                // if

            {
                arr[k] -= min;
            }


        }
    }

    public static void main(String[] args) {
        //int input[] = {10, 2, 10, 2, 10};// 5
        //int input[] = {2, 2, 2, 3, 3};// 5
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- != 0) {
            int zeros = 0;
            int n = sc.nextInt();
            int input[] = new int[n];
            int min = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                input[i] = sc.nextInt();

                if (min > input[i]) {
                    min = input[i];

                }

                if (input[i] == 0) {
                    zeros++;
                }
            }

            //subtract minimum element from array
            int count = 0;

            if (zeros == 0) {
                count += min;
                subtractmin(input, 0, n, min);

            } else {
                count += min;
                subtractmin(input, 0, n, min);

            }

            //traverse the array and findsubarrays between 0's
            //1) if an element is surrounded by 0's it will be destroyed at once separately
            // 2) also if length of subarray<min element, they all need to be destroyed separately
            // 3) if min<length of subarray they need to be destroyed at once with count+=min
            int i = 0, j = 0;

            while (true) {
                //move i to the first non zero element

                for ( i = 0; i < n; i++) {
                    if (input[i] != 0) {

                        break;
                    }
                }

                //means whole array is 0;
                if (i == n) {
                    System.out.println(Math.min(count, n - zeros));

                    break;
                }

                ///start with the first non zero element and fin
                for (j = i; j <= n; j++) {
                    if ( j == n || input[j] == 0) {
                        // take out min element
                        int minEle = findmin(input, i, j)  ;
                        //if min lement is greater than subarray size, destroy separately
                        count += Math.min(minEle, j - i);

                        //System.out.println("count="+count+"min element="+minEle);
                        // subtract minimum element
                        subtractmin(input, i, j, minEle);

                    }

                    //if last elemnt is not zero



                }


            }
        }
    }
}

Answer 1

你有的问题不是在代码上，而是在算法上。如果段的大小足够小，那么您必须执行移动2。但是，这个条件也不是不可缺少的。

在实践中，一个简单的递归方法可以解决这个问题。在给定段[k,l]中,减去最小值后,只需执行以下操作：

n_moves  = min (n, vmin + min_moves(x, k, l));

在下面，一个函数检测零点的位置并求和对应于每个段的移动，另一个函数被调用用于每个内部没有零点的段。

1 2 7  : 3
2 2 2 3 3  : 3
10 2 10 2 10  : 5
1 1 1 2 4 5 7 7 8 9  : 8

#include    <iostream>
#include    <vector>
#include    <algorithm>

std::vector<int> get_zeros (const std::vector<int> &x, int k, int l) {
    std::vector<int> zeros;
    for (int i = k; i <= l; ++i) {
        if (x[i] == 0) zeros.push_back(i);
    }
    return zeros;
}

int min_moves (std::vector<int> &x, int k, int l);

//  This function is called after detection the position of the zeros -> no zero inside
int min_moves_no_zero (std::vector<int> &x, int k, int l) {
    int n = l-k+1;
    if (n == 0) return 0;
    if (n == 1) return 1;
    int vmin = 10000;
    for (int i = k; i <= l; ++i) {
        if (x[i] < vmin) vmin = x[i];
    }
    for (int i = k; i <= l; ++i) {
        x[i] -= vmin;
    }
    
    int nm = std::min (n, vmin + min_moves(x, k, l));
    
    return nm;
}
    
//  This function detects positions of the zeros and sum the moves corresponding to each segment
int min_moves (std::vector<int> &x, int k, int l) {
    auto zeros = get_zeros (x, k, l);
    if (zeros.size() == 0) return min_moves_no_zero (x, k, l);
    int start = k;
    int total = 0;
    for (int z = 0; z < zeros.size(); ++z) {
        int end = zeros[z] - 1;
        if (start != zeros[z]) {
            total += min_moves_no_zero (x, start, end);
        }
        start = end + 2;
    }
    if (start <= l) {
        total += min_moves_no_zero (x, start, l);
    }

    return total;
}

void print (const std::vector<int> &x) {
    for (auto k: x) {
        std::cout << k << " ";
    }
}

int main() {
    std::vector<std::vector<int>> input {
        {1, 2, 7}, 
        {2, 2, 2, 3, 3},
        {10, 2, 10, 2, 10},
        {1, 1, 1, 2, 4, 5, 7, 7, 8, 9}
    };
    
    for (auto& arr: input) {
        auto save = arr;
        int moves = min_moves (arr, 0, arr.size()-1);
        print (save);
        std::cout << " : " << moves << "\n";
    }
}