牛客 NC21653 巨型迷宫 （枚举 + 贪心）

牛客 NC21653 ： NC21653 巨型迷宫

标签是贪心题， 但是我这个解法并没有多大的体会到贪心的思想。 实际上也就是枚举情况了

图片太长， 题目大意：

有 n 行。每行的代表的数不相同，同一行的数全部一样（行可理解成无限长）
同时给定四个点 ( s x , s y ) (sx, sy) (sx,sy)， ( e x , e y ) (ex, ey) (ex,ey)，分别代表 起点和终点。

需要算出起点到终点的路径上的数字和最少

注意数据范围 >> int 存储 sum 必然是不行的了…

但是很奇葩，int 竟然连 dis （sy 到 ey 的桥梁距离） 也存不下 >> 这种题这样玩就没意思了 >> dis 也需要 long 类型

枚举解法

思路：

1. 枚举所有行，以当前行作为中间桥梁， 计算 起点 sy 到 终点 ey 的距离上的和
2. 计算当前行到起点行 and 终点行的行之间距离
3. 更新最小值 sum

需要当前行计算到 起点、终点的行之间距离 >> 理解

枚举

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

public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int sx = in.nextInt();
        int sy = in.nextInt();
        int ex = in.nextInt();
        int ey = in.nextInt();
        
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        
        long ans = Long.MAX_VALUE;
        
        // 这个 dis 需要 long 类型， 不然过不了 .... 神奇
        long dis = abs(sy - ey) + 1;
        // 暴力模拟
        for(int i = 0; i < n; i++){
            // 遍历所有行
            // 横向相加
            long sum = dis * arr[i];
            
            // 竖项
            // 以 sx 为起点， 可以先走到上面再下来回到终点.
            sum += getColSum(arr, i, sx);
            // 去掉当前行的，因为上面已经加上了
            sum -= arr[i];
            
            sum += getColSum(arr, i, ex); // 终点
            sum -= arr[i];
            
            ans = min(ans, sum);
        }
        
        out.println(ans);
    }
    
    // 计算各行一列下来的和
    public static long getColSum(int[] arr, int i, int j){
        long sum = 0;
        int top = min(i, j);
        int bot = max(i, j);
        while(top <= bot){
            sum += arr[top];
            top++;
        }
        return sum;
    }

    
}