牛客 NC21222 道路铺设 （模拟 / 贪心）

牛客 NC21222： 道路铺设

贪心题，不能排序

根据给定的序列，各个数代表每段路的下陷深度，问最少需要多少天可以将所有数变为 0 （下陷路段填充完）

思路：

1. 使用 c n t cnt cnt 记录初始数组 0 的个数
2. 当 c n t cnt cnt 记录的 0 个数还没到数组长度时， 说明还需要继续填充。
3. 每次将前置 0 跳过
4. 从当前位开始， 找到遇到下一个 0 之前的最小值 m n mn mn。
5. 之后遍历到下一个 0 之前，之间的路段都减去最小值 m n mn mn， 相应的添加 增加 m n mn mn 天

AC Code

import java.util.*;
import static java.lang.System.out;

public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] deep = new int[n];
        int mxv = Integer.MAX_VALUE;
        
        int cnt = 0;
        for(int i = 0; i < n; i++){
            deep[i] = in.nextInt();
            if(deep[i] == 0) {
                deep[i] = mxv;
                cnt++;
            }
        }
        
        int ans = 0;
        
        // 记录前面都是 0 的位置
        int prezero = 0;
        // 当list 中 0 的个数小于 n
        while(cnt < n){
            int index = prezero;
            
            // 跳过前置 0 
            while(index < n && deep[index] == mxv) index++; 
            prezero = index;
            
            int mn = getMin(deep, index);
            while(index < n && deep[index] != mxv){
                deep[index] -= mn;
                if(deep[index] == 0) { deep[index] = mxv; cnt++; }
                index++;
            }
            
            // 第二天
            ans += mn;
        }
        out.println(ans);
        
    }
    
    // 找到起点的最小值
    public static int getMin(int[] arr, int s){
        if(s >= arr.length) return 0;
        int res = arr[s];
        s++;
        while(s < arr.length && arr[s] != Integer.MAX_VALUE){
            res = Math.min(res, arr[s]);
            s++;
        }        
        
        return res;
    }
}

---

贪心

第一个加上，之后找相邻的后一个比前一个大的长度.

import java.util.*;
import static java.lang.System.out;

public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] deep = new int[n];
        int mxv = Integer.MAX_VALUE;
        
        for(int i = 0; i < n; i++){
            deep[i] = in.nextInt();
        }
        
        int ans = deep[0];
        for(int i = 1; i < n; i++){
            if(deep[i] > deep[i - 1]){
                ans += (deep[i] - deep[i - 1]);
            }
        }        
        out.println(ans);
    }

}