P4801 [CCO 2015]饥饿的狐狸

$Result$

$Hyperlink$

https://www.luogu.com.cn/problem/P4801

$Description$

有$n$个东西，第$i$个物品的温度是$a_i$，有一杯温度为$w$的水（你可以认为它的水量无穷）

吃掉每个物品的代价是这次吃的物品的温度与上次吃的物品的温度差值，在每次吃东西的时候，你也可以选择先喝一杯水，这样就默认你上次吃的物品是水

假设你已经喝了一杯水，试着安排一种吃东西的顺序，使得代价最小/最大

数据范围：$n\le 10^5,w\le 10^9$

$Solution$

贪心，排序是显而易见的

考虑最大价值，显然我们是每次选择最大的和最小的判断即可，中间判断是否喝水更优就好了，注意初始化要喝一杯水

最小价值显然是升序或者倒序吃东西，如果没有喝水的限制，答案显然是$a_n-a_1$

考虑水的温度对答案的贡献
假设$w\in [a_1,a_n]$，显然我们可以在最后一个与$a_1$相等的食物后面喝一杯水，就能抵消刚开始喝的那杯水产生的代价，即答案为$a_n-a_1$
假设$w<a_1$，由于题目要求那杯水必须喝，所以答案要加上$a_1-w$，答案变成$a_n-w$
假设$w>a_n$，跟上面的一个道理，此时我们反过来吃，答案要加上$w-a_n$，答案变成$w-a_1$

最终化成的式子就是 max ⁡ { 0 , a n − w } + max ⁡ { 0 , w − a 1 } \max\{0,a_n-w\}+\max\{0,w-a_1\} max{0,an​−w}+max{0,w−a1​}

时间复杂度：$O(n\log n)$

$Code$

#include<cstdio> 
#include<cctype>
#include<algorithm>
#define LL long long
using namespace std;
int n,lst;
LL maxn,w,a[100010],now,l,r;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();w=read();for(register int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n);printf("%lld ",max(0ll,a[n]-w)+max(0ll,w-a[1]));lst=w;l=1;r=n;now=0;for(register int i=1;i<=n;i++) if(i&1) now+=max(abs(a[l]-lst),abs(a[l]-w)),lst=a[l++];else now+=max(abs(a[r]-lst),abs(a[r]-w)),lst=a[r--];maxn=now;lst=w;l=1;r=n;now=0;for(register int i=1;i<=n;i++) if(i&1) now+=max(abs(a[r]-lst),abs(a[r]-w)),lst=a[r--];else now+=max(abs(a[l]-lst),abs(a[l]-w)),lst=a[l++];printf("%lld",max(maxn,now));
}