题目大意

狐狸有 $N$ 块温度分别为 $T_1, T_2, \dots, T_N$ 的饼干和无限量的温度为 $W$ 的水。每吃一块饼干时，美味度等于当前饼干温度与前一次食物（饼干或水）温度的绝对差值。狐狸可以按任意顺序吃饼干，也可以在任意时刻喝水。要求计算狐狸能获得的总美味值的最小值和最大值。

算法思路

核心思想

利用排序和贪心策略，通过分析温度序列的数学性质来优化计算。

最小美味值分析

要最小化总美味值，需要最小化相邻食物之间的温度变化：

排序温度序列：将饼干温度按升序排列

关键观察：最小值可以通过以下方式实现：

从水温 $W$ 开始，直接跳到温度最低的饼干

在相近温度的饼干之间移动（减少温差）

最后从温度最高的饼干回到水温 $W$

数学表达式：最小美味值 = $\max(0, W - T_{\min}) + \max(0, T_{\max} - W)$

当 $W$ 在饼干温度范围内时，最小美味值就是温度范围的宽度

当 $W$ 在范围外时，需要加上从 $W$ 到最近端点的距离

最大美味值分析

要最大化总美味值，需要创造最大的温度变化：

交替取极值策略：从温度序列的两端交替选取饼干

决策依据：每次选择与当前温度差异最大的饼干

比较左端饼干和右端饼干分别能产生的温差

选择温差更大的那个饼干

两种起始方案：

从最低温饼干开始，交替向两端扩展

从最高温饼干开始，交替向两端扩展

水温的利用：在计算温差时，始终考虑与水温 $W$ 的比较，选择更大的温差

算法流程

数据预处理

读入饼干温度和水温

对饼干温度进行升序排序

计算最小美味值

直接计算水温与温度范围两端点的关系

输出 $\max(0, W - T_1) + \max(0, T_N - W)$

计算最大美味值

方案一：从最低温饼干开始

初始化当前温度为 $T_1$

使用双指针从序列两端向中间交替选取

每次选择能产生更大温差的饼干

方案二：从最高温饼干开始

初始化当前温度为 $T_N$

同样采用双指针交替策略

取两种方案的最大值作为最终结果

输出结果

分别输出最小和最大美味值

复杂度分析

时间复杂度：$O(N \log N)$，主要开销来自排序操作

空间复杂度：$O(N)$，用于存储饼干温度数据

总结

本题展示了贪心算法在优化问题中的强大应用：

问题分析能力：通过数学分析发现最小值和最大值的计算规律

排序预处理：利用排序简化问题结构，便于极值操作

贪心选择策略：在最大值计算中采用交替取极值的方法

双指针技巧：高效实现从序列两端向中间的遍历

边界情况处理：妥善处理水温在饼干温度范围内外的情况

这种"排序 + 贪心选择"的解题模式适用于许多涉及距离优化和极值选取的问题，体现了通过深入分析问题结构来设计高效算法的重要性。该解法在 $N \leq 10^5$ 的数据规模下能够高效运行，展现了良好的可扩展性。