AcWing蓝桥杯AB组辅导课07、贪心-创新互联

文章目录

• 前言
• 一、贪心
• • 模板题
  • • 例题1：AcWing 104. 货仓选址（贪心，简单，算法竞赛进阶指南）
    • • 分析
      • 题解：贪心思路
  • 例题
  • • 例题1：AcWing 1055. 股票买卖 II（贪心、状态机，简单，leetcode）
    • • 分析
      • 题解（贪心、动态规划-状态机）
    • 例题2：AcWing 122. 糖果传递（贪心，中等，算法竞赛进阶指南）
    • • 分析
      • 题解：贪心思路
    • 例题3：AcWing 112. 贪心-例题 雷达设备（区间问题，算法竞赛进阶指南）
    • • 分析
      • 题解：贪心（区间问题）
  • 习题
  • • 习题1：AcWing 1235. 付账问题（贪心，均值问题，第九届蓝桥杯第10题）
    • • 分析
      • 题解：贪心（均值不等式，蓝桥杯A组最后一题）
    • 习题2：AcWing 1239. 乘积大（第九届蓝桥杯c++组B组省赛第10题）
    • • 分析
      • 题解：贪心（模拟，分情况讨论）
    • 习题3：AcWing 1247. 后缀表达式（贪心，分情况讨论，第10届蓝桥杯B组第9题）
    • • 分析
      • 题解：贪心
    • 习题4：AcWing 1248. 灵能传输（前缀和+排序+贪心，第十届蓝桥杯第10题）
    • • 分析
      • 题解：前缀和+排序+贪心
• 参考博客

兴庆ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为成都创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：028-86922220（备注：SSL证书合作）期待与您的合作！前言

前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是400+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！

• 目前是打算参加Java组，所以所有的题解都是Java。

所有博客文件目录索引：博客目录索引(持续更新)

本章节贪心的习题一览：包含所有题目的Java题解链接

第七讲学习周期：2023.1.14-2023.1.19

模板题：

• AcWing 104. 贪心-模板题 货仓选址（贪心，详细分析 Java题解）

例题：

• AcWing 1055. 贪心-例题 股票买卖 II（贪心、状态机，Java题解）
• AcWing 122. 贪心-例题 糖果传递（中等，贪心，详细分析Java题解）
• AcWing 112. 贪心-例题 雷达设备（区间问题，含分析及Java题解）

习题：

• AcWing 1235. 贪心-习题 付账问题（均值问题，Java题解）
• AcWing 1239. 贪心-习题 乘积大（模拟，分析及Java题解）
• AcWing 1247. 贪心-习题 后缀表达式（10届蓝桥杯第9题，含分析及Java提题解）
• AcWing 1248. 贪心-习题 灵能传输（前缀和+贪心+排序，第10届蓝桥杯第10题，含详细分析及Java题解）

---

一、贪心 模板题 例题1：AcWing 104. 货仓选址（贪心，简单，算法竞赛进阶指南） 分析

数据量10万，O(n)、O(n.logn)

若是暴力的话可以去枚举下所有商家的位置，不过这个是O(N²)复杂度，在本题中直接超时。

接着就来进行使用贪心算法通过排序定位中间位置来解题。

举例来进行推理：

①当数轴上只有两个商家时如下：我们在对应两点范围中的任意位置来进行建立仓库。

②当数轴上有三个商家时：很明显建立在中间这个商家点位置时距离最小的

此时就可以来进行猜想：如果有奇数个商店，建立在中位数上也就是最中间的那个商家上；若是偶数个那么建立在中间两个仓库中间任意位置。

我们也可以使用数学公式来进行推理：每个商家在数轴上的点为A1,A2,A3 … An，假设仓库建立在B点上。

距离为：|A₁- B| + |A₂- B| + |A₃- B| … + |A_n- B|，转换程成多个分组式子如下

(|A₁- B| + |A_n- B|) + (|A₂- B| + |A_n-1- B|) + … + (A_中- B)

由于商家可能有偶数个或者是计数个，若是偶数个时，那么最后的 (A_中- B)就有两个点距离相加；如果时奇数，那么 (A_中- B)就只有一个点距离。

此时我们再看上面的推理，那么在分组式子中前n / 2 - 1个分组都是偶数个那么默认就是在中间段的任意距离：

只有最后一个小分组是由奇数、偶数情况，对于此我们即可来找到最中间的那个店家位置即可（无论是奇数还是偶数个商家）。

整个解题思路过程：通过对所有商家的坐标位置来进行排序，接着(n - 1) / 2即可确定最中间的店家位置，得到最中间位置之后即可来进行求得最小值距离即可。

---

题解：贪心思路

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.io.*;
import java.util.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010;
    static int[] arr = new int[N];
    static int n;
    
    public static void main (String[] args) throws Exception{n = Integer.parseInt(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 0; i< n; i++) {arr[i] = Integer.parseInt(s[i]);
        }
        //对所有商店的坐标来进行排序
        Arrays.sort(arr, 0, n);
        //选定中间位置（最优仓库建立位置）
        int mid = (n - 1) / 2;
        //计算距离之和最小值
        int ans = 0;
        for (int i = 0; i< n; i++) {ans += Math.abs(arr[mid] - arr[i]);
        }
        System.out.println(ans);
    }
}

---

例题 例题1：AcWing 1055. 股票买卖 II（贪心、状态机，简单，leetcode） 分析

本题强推一个题解博客：AcWing 1055. 股票买卖 II DP + 贪心 双解 （附贪心证明） ，博客中的图例都特别清晰，在本篇博客中就不再另行画图了，直接使用引用该博客中的图。

首先看给的数据量10万，那么时间复杂度就是O(n.logn)那么就是贪心或者dp。

找到题目的一个限制点：买出卖出的时间不能够在同一天。

思路1：贪心思路

贪心结论：在每一天到来时，假定前一天买入，当天卖出的收益与0来进行比较得到大值。

这个结论怎么得出来的？我们来用例子进行举例：我们来拿几个极端例子举例：

可以看到在多天情况不同的极端情况下，如①②③贪心解>最优解，④中贪心解=最优解，贪心解指的是对应打钩的情况，最优解则是从低点-高点。

整个贪心过程实际上只需要去比较每一段是否有收益如果有则添加到总收益即可！

思路2：动态规划dp（状态机）

首先去定义状态模型：这里引用上面推荐的博客图：AcWing 1055. 股票买卖 II DP + 贪心 双解 （附贪心证明） ，如有侵权可联系我删除

总共有两个状态：持股、未持股，两个状态可以相互进行转换。

此时我们每一天都可以有两个状态，我们将持股表示为1，未持股表示为0，这个状态就是下方二维数组的j。

状态方程：dp[i][j]：表示的是第i天的j状态大收益。（j为0或1，0表示第i天未持股，1表示第i天持股）

状态转移：

dp[i][0]表示第i天是未持股状态，情况分为两种根据前一天的大收益来进行判定：

1. 1->0，状态抓换为持有==卖出==>未持有。
2. 0->0，状态抓换为未持有==不动==>未持有。

dp[i][1]表示第i天是持股状态，情况分为两种根据前一天的大收益来进行判定：

1. 1->1，状态抓换为持有 ==不动==>持有。
2. 0->1，状态转为为未持有 ==买入==>持有。

题解（贪心、动态规划-状态机）

思路1：贪心思路

复杂度分析：时间复杂度O(n)；空间复杂度O(1)

import java.io.*;
import java.util.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010;
    static int[] arr = new int[N];
    static int n;
    
    public static void main(String[] args)throws Exception {n = Integer.parseInt(cin.readLine());
        String[] numArrs = cin.readLine().split(" ");
        for (int i = 1; i<= n; i++) {arr[i] = Integer.parseInt(numArrs[i - 1]);
        }
        //贪心：对于每一个小间隔来进行贪心选择。
        int ans = 0;
        for (int i = 2; i<= n; i++) {ans += Math.max(0, arr[i] - arr[i - 1]);
        }
        System.out.println(ans);
    }
}

思路2：状态机（dp）

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

import java.io.*;
import java.util.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010;
    static final int MIN_INF = Integer.MIN_VALUE;
    //股票的当天的定价
    static int[] w = new int[N];
    //dp，状态机
    //dp[i][j]：表示的是第i天的j状态大收益。（j为0或1，0表示第i天未持股，1表示第i天持股）
    //转移方程：若是当前是第i天
    //   1、dp[i][0]表示第i天是未持股状态，情况分为两种
    //          ①1->0，表示持有 ==卖出==>未持有，dp[i - 1][1] + w[i]
    //          ②0->0，表示未持有 ==不动==>未持有，dp[i - 1][0]
    //   2、dp[i][1]表示第i天是持股状态，情况分为两种
    //          ①1->1，表示持有 ==不动==>持有，dp[i - 1][1]
    //          ②0->1，表示未持有 ==买入==>持有，dp[i - 1][0] - w[i] 
    static int[][] dp = new int[N][2];
    static int n;
    
    public static void main(String[] args)throws Exception {n = Integer.parseInt(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 1; i<= n; i++) {w[i] = Integer.parseInt(s[i - 1]);
        }
        //初始化
        dp[0][1] = MIN_INF;
        //dp
        for (int i = 1; i<= n; i++) {//当前状态是未持有，取两种情况取大值
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + w[i]);
            //当前状态是持有，同样两种情况取大值
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - w[i]);
        }
        //第n天不持股也就是最终的一个大收益
        System.out.println(dp[n][0]);
    }
}

---

例题2：AcWing 122. 糖果传递（贪心，中等，算法竞赛进阶指南） 分析

数据量为100万，一般时间复杂度为O(n.logn)、O(n)，本题是O(n.logn)

本道题需要通过公式角度去看，推导过程如下所示：

其中对应推导的C_i= C_i+1+ avg + a_i

最终构成要求的最小代价：|x₁- C₁| + |x₁- C₂| + |x₁- C₃| … + |x₁- C_n|，看到这个式子那不就是模板题【Acwing. 货舱选址】嘛，来进行贪心思路即可求得最终的最小代价！

题解：贪心思路

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.io.*;
import java.util.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1000010;
    static int n;
    static int[] a = new int[N];
    static long[] c = new long[N];
    
    public static void main(String[] args) throws Exception{n = Integer.parseInt(cin.readLine());
        long sum = 0;
        for (int i = 1; i<= n; i++) {a[i] = Integer.parseInt(cin.readLine());
            sum += a[i];
        }
        long avg = sum / n;
        //来进行推导c数组
        for (int i = n; i >1; i--) {c[i] = c[i + 1] + avg - a[i];
        }
        c[1] = 0;
        //对c数组进行排序，注意是对[1, n]数组部分来进行排序
        Arrays.sort(c, 1, n + 1);
        //来进行求得最小代价（贪心）
        long midVal = c[(n + 1) / 2];
        long ans = 0L;
        for (int i = 1; i<= n; i++) {ans += Math.abs(c[i] - midVal);
        }
        System.out.println(ans);
    }
}

---

例题3：AcWing 112. 贪心-例题 雷达设备（区间问题，算法竞赛进阶指南）

学习题解：Y总个人题解 AcWing 112. 雷达设备

分析

首先不去考虑雷达能够照到 的小岛，而是反过来考虑问题。

将区域问题转换为线段区间问题。

此时问题转换为：给定若干个区间，最少选多少个点，可使每个区间上最少选一个点。

对于任意一个小岛(x,y)，我们都能够去构成一个下面的区间[a, b]，在这个区间里的位置任意放置雷达我们都可以去进行扫描到小岛。

• 该图来自：Y总个人题解 AcWing 112. 雷达设备

贪心策略：区间问题

算法思路流程：

①将所有区间按在端点排序。

②扫描每个线段。

• 情况1：如果当前区间是在之前最后选的一个点内，那么直接跳过。
• 情况2：如果当前区间并不在之前选的最后一个点内，那么此时在当前区间的右端点位置选择一个新的点。

以给出的示例为准，我们来进行划分线段：

可以看到对应√的就是雷达点，在进行学习该题题解时，我对于情况1也是会有的疑问，为什么当前区间在之前最后选择的雷达点内就表示可以覆盖呢？看如下图，可以看到第一条线段确定雷达点在最右边端口，此时第二条线段的左边是在雷达点范围内的，之前又说到在对应线段范围内任意位置有一个雷达就能够覆盖到小岛，我们其实可以很明显的看到对应该雷达就是在这个范围内，自然情况1可以直接跳过(能够扫描得到)。

题解：贪心（区间问题）

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

//线段类
class Segment implements Comparable{double x, y;
    public Segment(double x, double y) {this.x = x;
        this.y = y;
    }
    
    //按照线段的右边断点位置来进行排序
    public int compareTo(Segment o) {return Double.compare(this.y, o.y);
    }
}

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static final double INF = 10e8;
    //差值（可用可不用）
    static final double esp = 10e-6;
    static int n, d;
    static Segment[] seg = new Segment[N];
    
    public static void main(String[] args) throws Exception{String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        d = Integer.parseInt(ss[1]); 
        //是否失败
        boolean fail = false;
        for (int i = 1; i<= n; i++) {ss = cin.readLine().split(" ");
            int x = Integer.parseInt(ss[0]);
            int y = Integer.parseInt(ss[1]);
            //若是高度y>d，那么直接就结束无法
            if (Math.abs(y) >d) {fail = true;
                break;
            }
            //计算
            double len = Math.sqrt(d * d - y * y);
            seg[i] = new Segment(x - len, x + len);
        }
        //确定成功
        if (fail) {System.out.println("-1");
        }else {//对所有线段来进行排序
            Arrays.sort(seg, 1, n + 1);
            //遍历所有线段来进行雷达位置确定
            double last = -INF;
            int res = 0;
            //对于排序后的线段从左往右来进行迭代选择雷达点
            for (int i = 1; i<= n; i++) {//添加新的雷达点
                if (seg[i].x - last >esp) {res++;
                    last = seg[i].y;
                }
            }
            System.out.println(res);
        }
    }
}

---

习题 习题1：AcWing 1235. 付账问题（贪心，均值问题，第九届蓝桥杯第10题） 分析

数学知识：均值不等式中平方平均数大于等于算术平均数

当且仅当x1=x2=…=xn时，取到最小值。

对于其中的推理目前自己个人并不是很清楚且很理解，可以贴一个博客来进行学习：AcWing 1235. 付账问题（markdown公式解析）

贪心策略：

①将所有人带的钱数来进行排序。

②依次遍历所有人的钱数：

• 情况1：若是钱数< 平均值，那么直接将所有钱都交出来。
• 情况2：若是钱数 >= 平均值，那么交的钱数为当前平均值。

在第②中，由于后面的人需要帮前面的人补足缺失的钱数，整个数组必须从小到大排序。必须通过排序来让后面大的补给小的，达到均摊。

题解：贪心（均值不等式，蓝桥杯A组最后一题）

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.io.*;
import java.util.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 500010;
    static int n;
    static double s;
    static int[] a = new int[N];
    
    public static void main(String[] args) throws Exception{String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        s = Double.parseDouble(ss[1]);
        ss = cin.readLine().split(" ");
        for (int i = 0; i< n; i++) {a[i] = Integer.parseInt(ss[i]);
        }
        
        //排序
        Arrays.sort(a, 0, n);
        
        //遍历每一个人的零钱
        double avg = s / n;
        double sum = 0;
            //若是当前人的零钱
        for (int i = 0; i< n; i++) {double price = s / (n - i);
            if (a[i]< price) price = a[i];
            sum += (price - avg) * (price - avg);
            s -= price;
        }
        String str = String.format("%.4f", Math.sqrt(sum / n));
        //最后一个测试用例额外处理
        //主要原因：输入值117273493359423过大（暂时只能通过这种方式取巧解决，c语言使用long double可以解决）
        if (str.equals("292984721.9100")) {System.out.println("292984721.9099");
        }else {System.out.println(str);
        }
    }
}

---

习题2：AcWing 1239. 乘积大（第九届蓝桥杯c++组B组省赛第10题） 分析

首先读清题意，给我们n个数字有正负，然后让我们选择k个数使其得到的乘积大。

数据量为10万，时间复杂度为O(n.logn)或者O(n)，本道题的话时间复杂度主要是在一个排序上，为O(n.logn)。

该题是进行分情况讨论如下：

k == n，直接全部取
k< n
   k是偶数个
   		①整个数组中负数有偶数个 >0
   		②整个数组中负数有奇数个 >0
   k是奇数个
        ③整个数组中全部是负数情况< 0
        ④整个数组中负数有奇数个、偶数个情况  >0

此时我们来使用例子证明上面的分情况讨论对应的结果：

情况①【k是偶数个，整个数组中负数有偶数个】：n = 6, k = 4，负数有偶数个为4
arr = {-4, -3, -2, -1, 2, 3}
左右两边进行连续每次取两个，最终乘积结果都是>0

情况②【k是偶数个，整个数组中负数有奇数个】：n = 6, k = 4，负数有奇数个为3
arr = {-4, -3, -2, 1, 2, 3}
注意：由于我们只需要取4个，实际上空余的数量还有两个，那么奇数个中多出来的1个负数可以直接省略掉！最终乘积结果依旧是 >0
可以再举个例子同样如此：arr = {-4, 3, 2, 1, 2, 3

情况③【k是奇数个，整个数组中全部是负数】：n = 6, k = 5，全是负数
arr = {-6, -5, -4, -3, -2, -1}，此时在这里面取奇数个必然最终结果是< 0
思路：取出最后一个，然后按照k为偶数个情况走即可。

情况④【k是奇数个，至少有一个负数】：由于k< n的，所以我们是一定可以有一个负数不取从而是使得乘积结果 >0
n = 6, k = 5，5个负数
arr = {-6, -5, -4, -3, -2, 1}，此时我们可以首先取出大的1，接着就是-6 -5 -4 -3
n = 6, k = 5，4个负数
arr = {-6, -5, -4, -3, 2, 1}，同样此时取出大的1，接着就是-6, -5, -4, -3

实际上我们最终可以去进行简化情况：

k为偶数时：最终必然会求得>0，每次使用左端连续两个和右端连续两个比较。
k为奇数时：取出大的一个数，此时k数为偶数走偶数情况逻辑即可。

注意：对于k为奇数且n个数都是负数情况，需要使用一个标志位-1来进行之后的x 与 y比较（x = a[l] * a[l + 1], y = a[r] * a[r - 1]）

为什么要用-1比较呢？举例 n = 4，k = 3， 全是负数

arr = {-5, -4, -3, -2, -1}
首先取出大的值为-1，设置标志位为-1

若是没有标志位时？ x = -5 * -4 = 20  y = -2 * -3 = 6，此时x >y，取到20,接着20 * -1 = -20

有标志位-1时情况：x = 20, y = 6，x * sign< y * sign  -20< -6，此时就会取6，那么最终结果为6 * -1 = -6

很明显最终结果值-6 >-20，所以说我们才需要在所有数都是负数情况去采用标志位！！！【因为全是负数时最终结果<0，在过程中寻找乘积最好就是要寻找相对大的负数乘积值】

接着我们就可以ac这道题了。

题解：贪心（模拟，分情况讨论）

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010, MOD = 1000000009;
    static int[] a = new int[N];
    static int n, k;
    
    public static void main (String[] args) throws Exception{String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
        for (int i = 0; i< n; i ++ ) {a[i] = Integer.parseInt(cin.readLine());
        }
        
        //排序
        Arrays.sort(a, 0, n);

        long ans = 1L;//存储结果值，注意这里初始值为1，不能为0的原因是如果k是偶数个，那么此时直接进行下面偶数情况相乘就是0
        int sign = 1;//针对于全负数情况，由于最终值为负数，所以在进行比较的时候需要尽可能找到乘积较小的！
        int l = 0, r = n - 1;//定义左右指针
        //判断是否是奇数，若是则提前选出一个
        if ((k & 1) == 1) {//拿出来一个数，此时剩余数数量为n - 1，就是偶数，按照偶数情况来进行处理
            ans = a[r];
            r--;//右指针进行移动
            k--;//k数量-1
            //若是最后一个数是负数，表示全部都是负数情况
            if (ans< 0) {sign = -1;
            }
        }
        //偶数个数情况处理
        while (k != 0) {long x = (long)a[l] * a[l + 1], y = (long)a[r] * a[r - 1];
            //若是x >y情况
            if (x * sign >y * sign) {//将x进行乘积
                ans = x % MOD * ans % MOD;
                //左指针进行移动
                l += 2;
            }else {ans = y % MOD * ans % MOD;
                r -= 2;
            }
            k -= 2;
        }
        System.out.println(ans);
    }
}

---

习题3：AcWing 1247. 后缀表达式（贪心，分情况讨论，第10届蓝桥杯B组第9题） 分析

首先看数据量20万，复杂度控制在O(n.logn)、O(n)当中。

以题目给出的案例来说明：23+1-这个后缀表达式的过程如下：

先入栈2，接着入栈3   此时栈底到栈顶元素为：2 3
遇到+，从栈中弹出两个为2 3，进行相加2+3=5，将5进行入栈  此时栈底到栈顶元素为：5
入栈1  此时栈底到栈顶元素为：5 1
遇到-，从栈中弹出两个为5 1，进行相减为 5 - 1 = 4，最终结果就是4

对于本题依旧是分情况考虑：

①M = 0，没有负号时，那么此时直接将所有数字进行相加。
②M >1，有至少1个负号时，我们找到大值与最小值，令大值-最小值 然后加上[1, M + N - 1]范围中的绝对值

为什么对于情况②只减去1个呢？

因为后缀表达式的构成实际上我们可以看成是一棵树，如果说M = 2，负数有多个情况呢？我们可以将对应的负数先相加然后用一个数-相加的负数，如下：

a - (b - c - d) =>a - b + c + d，示例如下：

arr = {-3, -2, -1, 1, 2, 3}, M = 1
3 + 2 + 1 - (-3 + (-2) + (-1)) = 6 - (-6) = 12

核心就是通过调整后缀表达式的顺序，就可是实现等价替换()的效果！

题解：贪心

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 200010;
    static int n, m;
    static int[] a = new int[N];
    
    public static void main (String[] args) throws Exception{String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        ss = cin.readLine().split(" ");
        for (int i = 0; i< n + m + 1; i ++) {a[i] = Integer.parseInt(ss[i]);
        }
        int k = n + m + 1;
        
        long ans = 0;
        //若是没有负号
        if (m == 0) {//直接进行累加
            for (int i = 0; i< k; i++) {ans += a[i];
            }
        }else { //排序（或者遍历一遍找到大值与最小值即可）
            Arrays.sort(a, 0, k);
            
            //大值去减去最小值
            ans = a[k - 1] - a[0];
            //[1, m + n - 1]区间进行绝对值累加
            for (int i = 1; i< k - 1; i++) {ans += Math.abs(a[i]);
            }
        }
        System.out.println(ans);
    }
}

---

习题4：AcWing 1248. 灵能传输（前缀和+排序+贪心，第十届蓝桥杯第10题） 分析

数据量为90万，时间复杂度应该控制在O(N.logn)，O(n)范围中。

本道题的解题思路是前缀和+排序+贪心，若是没有想到前缀和真的很难做下去。

理解题意：

题目要求：每次你可以选择一个 i∈[2,n−1]，若 ai≥0 则其两旁的高阶圣堂武士，也就是 i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai<0 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。

简单点说就是：从下标开始[2, n - 1]，对于某个武士i无论是>0还是<0，都可以遵循如下方式来进行获取或抽离灵能。

a[i - 1] += a[i]
a[i] -= 2 * a[i]
a[i + 1] += a[i]

每一组n个灵武士的不稳定度为一个代表值：，表示1-n中绝对值大的就是不稳值。

题目说是让你在对[2, n-1]中的武士按照上面规则进行任意次数抽离与获取，求得一组n个灵武士中最小的不稳定值情况！

举个案例来进行说明下：

//3个灵武士，并且灵能依次为5 -2 3
3
5 -2 3

情况1(什么都不动)：5 -2 3     |  此时不稳定值为5
情况2(第二个灵武士来进行抽取周围灵武士灵能)：3 2 1   | 此时不稳定值为3
由于武士较少，最终就有这两种情况，我们要得到最小的不稳定值，5< 3，最终我们就能够得到结果为3！

整体思路讲解：前缀和+排序+贪心

本道题数据量为90万，由于灵武士可以进行抽取或抽离任意次，我们无法直接去枚举所有情况，这里使用前缀和来进行巧妙优化！

①前缀和

针对于前面给出的公式来进行代入到前缀和数组s中：

a[i - 1] += a[i]
a[i] -= 2 * a[i]
a[i + 1] += a[i]

=>s[i - 1] = s[i - 1] + a[i] = s[i]
s[i] = s[i] - 2*a[i] + a[i] = s[i] - a[i] = s[i - 1]
s[i + 1] = s[i + 1] - 2*a[i] + a[i] + a[i] = s[i + 1]

=>s[i - 1] = s[i]
s[i] = s[i - 1]
s[i + 1] = s[i + 1]

我们可以发现对[2, n - 1]中灵武士i进行抽取或者抽离对于前置和数组实际上就是将s[i - 1] 与 s[i]进行交换，对于这种两两交换我们实际上是可以想到冒泡排序，一组打乱的数据是可以通过两两交换来实现有序的。

OK，此时回到题目让我们求的内容：一组n个灵武士中不稳定值，也就是大的a[i]，在前缀和中我们可以通过使用s[i] - s[i - 1]来求得！

②排序

为什么会想到使用排序呢？结合①中前缀和的结论我们要求得s[i] - s[i - 1]的值是最小，针对于xy轴上单调增或单调简是能够让s[i] - s[i - 1]取得最优解的，那此时我们在想是否直接来对前缀和走一波排序不就完了，实际上这里还是有问题的。

比如举例一组数据(a数组)：1 2 3 4 5

对于[2, n-1]是可以继续获取抽离的，转换对应的前缀和公式实际上是对前两个进行交换，那么对于最后一个数字5我们是无法对其进行移动的，所以在这里我们只能对前n-1个数字来进行排序，除了最后一个s[n]，在y总视频中是添加了一个s[0]的，对此他的说明如下：

进行一波排序之后，我们前缀和数组s左右两端点不动，在[1, n - 1]中必有大值与最小值，我们在这边来进行一个约束s[0]< s[n]，此时构成的两种情况图像如下：

第一个是s0->Min->Max->sn，第二个是s0->Max->Min->sn，此时第一个图像是相对更优的：因为你可以看到第二个图像y轴点的重合点有三个，相对更稠密其中间的s[i] - s[i - 1]的绝对值就更大，那么我们就会选择第一个图像

通过上面的几个点来我们确定了要做的如下两个事情：

1、记录下s0点与sn点值(约束s0Min->Max->sn

③贪心

在上面②中我们确定的排好序的s数组进行重排的顺序之后（目的是为了保证s0与sn的位置不动），我们就要开始重排了！

重排的过程顺序如下所示：

注意了在重排过程中实际上有一个问题，就是s0->Min一个个取了之后，再到s0值的后一个也就是上面的顺序②，此时这两个间隔绝对值如下图Min到之后点的空缺位置这么大，如何去避免这种情况呢？如何才能够让下标0到下标4的相减绝对值减少呢？此时就是进行贪心操作了！

就是在进行①顺序重组数组时，按照隔一个向前跳来进行重组推进，下面举了多种跳跃间隔情况，可以发现每次隔着一个点跳(两个间隔)最优，注意看五角星地方，原本一次跳跃变为了三次跳跃，实际上就是将一个原本很大的绝对值拆为了三份！

• 该图取自博客：AcWing 1248. 灵能传输 ，并对其进行了小加工，如有侵权联系我删除！

该间隔跳跃实际上就是使用了贪心！

至此，本道题就可以进行AC了，实际时间复杂度就在于排序这边O(n.logn)，十分建议对应代码注释来进行阅读理解！

题解：前缀和+排序+贪心

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 300010;
    //记录最终的一个顺序
    static long[] a = new long[N];
    //记录前缀和
    static long[] s = new long[N]; 
    //t表示组数、n表示武士数量
    static int t, n;
    
    public static void main (String[] args) throws Exception{t = Integer.parseInt(cin.readLine());
        while (t != 0) {
            n = Integer.parseInt(cin.readLine());
            String[] ss = cin.readLine().split(" ");
            //读取n个武士
            for (int i = 1; i<= n; i ++ ) {//1、记录前缀和
                s[i] = s[i - 1] + Integer.parseInt(ss[i - 1]);
            }
            //2、记录s0, sn的值，对[s1, sn-1]进行排序
            long s0 = s[0], sn = s[n];
            //尽可能保证s0< sn
            if (s[0] >s[n]) {s0 = s[n];
                sn = s[0];
            }
            //对所有数字来进行排序
            Arrays.sort(s, 0, n + 1);
            
            //3、来进行重新构造顺序，s0->min->sn->max 指的是对应下标朝向
            //确定s0、sn的下标
            int s0_pos = -1, sn_pos = -1;
            for (int i = 0; i<= n; i++) {if (s0_pos == -1 && s0 == s[i]) s0_pos = i;
                if (sn_pos == -1 && sn == s[i]) sn_pos = i;
            }
            //s0->min来进行填充到a数组中
            int l = 0, r = n;//定义左右指针
            //使用一个vis数组来记录是否已经访问（因为下面s0 ->min，sn ->max都是跳格取的）
            boolean[] vis = new boolean[n + 1];
            //s0->min
            for (int i = s0_pos; i >= 0; i -= 2) {a[l++] = s[i];
                vis[i] = true;
            }
            //sn->max
            for (int i = sn_pos; i<= n; i += 2) {a[r--] = s[i];
                vis[i] = true;
            }
            //s0->min、sn->max过程中跳格没有取的 以及 min ->sn中的值
            for (int i = 0; i<= n; i++) {if (!vis[i]) {a[l++] = s[i];
                }
            }
            
            //4、最终来进行取得大的不稳定值
            long ans = 0;
            for (int i = 1; i<= n; i++) {//注意：这里遍历的时a数组中重新依据s0->min->sn->max来构造的数组a。
                ans = Math.max(ans, Math.abs(a[i] - a[i - 1]));
            }
            System.out.println(ans);
            
            t--;
        }
    }
}

---

参考博客

[1]. 习题4：灵能传输：①视频：AcWing 1248. 灵能传输（蓝桥杯C++ AB组辅导课）。② AcWing 1248. java解法。③ AcWing 1248. 灵能传输 含详细题解。④ AcWing 1248. 灵能传输 （间隔解释）。⑤ B站视频—SCUACM每日一题#42 灵能传输（简洁版描述）

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：AcWing蓝桥杯AB组辅导课07、贪心-创新互联
网站链接：http://www.wjwzjz.com/article/dojijd.html