解题思路:
确实是一道很好的贪心，但由于加上了水这个影响因素，使题目复杂度上升了不少。（考虑的东西多了嘛）
- 输个入。
- 对饼干温度
无脑排序。 - 求最小值。
- 求最大值（用双指针做，后面会讲）。
解题过程:
先输入（这个步骤就不用我讲了）
int a[1000005];
long long n,ws;
long long minn=0,num=ws;
cin>>n>>ws;//输入饼干数和水温
for(int i=1;i<=n;i++)
cin>>a[i];
先排序！！
sort(a+1,a+n+1);
最容易的肯定就是最小值：
！其实题意一定要读懂，我个提醒也是我自己看错的：
每当他吃一块饼干时，这块饼干的美味度为当前饼干与吃/喝的前一样食物（包括饼干和水）的温度的差的绝对值。
- 那我们不妨分三种情况来考虑（ws 是水温）：
- 当水温小于等于饼干中温度的最小值，此时喝好水后，从饼干中最小值一直按顺序（单调升序，前面排好序了）吃到最大值 (\(a_1,a_2\cdots a_n\)) 就是累计美味值最小的。
if(ws<=a[1]){
minn=a[n]-ws;
}
- 水温大于等于饼干中温度的最大值时，喝好水后，按单调降序 (\(a_n,a_{n-1}\cdots a_1\)) 吃掉饼干可获得最小值。则有：
if(ws>=a[n]){
minn=ws-a[1];
}
- 当 \(a_1\le ws\le a_n\) 时，直接 \(a_n-a_1\) 即可：
if(ws>=a[1]&&ws<=a[n]){
minn=a[n]-a[1];
}
那么接下来是最大值：
前面也提到了要用双指针做，具体怎么实现呢？
先定义两个指针：
t1=1;t2=n;
因为排好序后，\(a_n-a_1\) 的跨度最大，然后 \(a_1-a_{n-1}\)，再是 \(a_{n-1}-a_2\cdots\)，以此类推，两个指针依次向中间靠拢，就可算出最大的美味值和了。
但是此时要考虑两点：
- 喝好水后应该先吃 \(a_n\) 还是 \(a_1\)。
- 在双指针的过程中，判断是喝了水后吃下一个饼干的美味值大还是直接吃美味值大。
所以我们要循环两次，分别为先吃 \(a_1\) 和先吃 \(a_n\)，并在过程中判断上面所说的第2点。
则有
long long num=ws;//存储上一个食物的温度
long long ans2=0,ans=0;//分别分析取a[1]与a[n]为开头的情况(找最优解);
ans+=abs(ws-a[t1]);
num=a[t1];//从a[1]开始
t1++;
for(int i=2;i<=n;i++){
if(i%2==0){
ans+=max(abs(num-a[t2]),abs(ws-a[t2]));
num=a[t2];
t2--;
}
else{
ans+=max(abs(num-a[t1]),abs(ws-a[t1]));
num=a[t1];
t1++;
}
}
t1=1;t2=n;//从a[n]开始
ans2+=abs(ws-a[t2]);
num=a[t2];
t2--;
for(int i=1;i<=n-1;i++){
if(i%2==0){
ans2+=max(abs(num-a[t2]),abs(ws-a[t2]));
num=a[t2];
t2--;
}
else{
ans2+=max(abs(num-a[t1]),abs(ws-a[t1]));
num=a[t1];
t1++;
}
}
ans=max(ans2,ans);//赋值最优解
到这里题就做完了，那——
AC 代码！：
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
long long n,ws;
cin>>n>>ws;//输入饼干数和水温
long long minn=0,num=ws;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);//排序！！！！
long long cnt=1;
long long t1=1,t2=n;
if(ws<=a[1]){//判断最小值
minn=a[n]-ws;
}
else if(ws>=a[n]){
minn=ws-a[1];
}
else{
minn=a[n]-a[1];
}
long long ans2=0,ans=0;//判断最大值，分别分析取a[1]与a[n]为开头的情况(找最优解);
ans+=abs(ws-a[t1]);
num=a[t1];//存储上一个食物或水的温度
t1++;
for(int i=2;i<=n;i++){
if(i%2==0){
ans+=max(abs(num-a[t2]),abs(ws-a[t2]));
num=a[t2];
t2--;
}
else{
ans+=max(abs(num-a[t1]),abs(ws-a[t1]));
num=a[t1];
t1++;
}
}
t1=1;t2=n;
ans2+=abs(ws-a[t2]);
num=a[t2];
t2--;
for(int i=1;i<=n-1;i++){
if(i%2==0){
ans2+=max(abs(num-a[t2]),abs(ws-a[t2]));
num=a[t2];
t2--;
}
else{
ans2+=max(abs(num-a[t1]),abs(ws-a[t1]));
num=a[t1];
t1++;
}
}
ans=max(ans2,ans);//取最优解
cout<<minn<<" "<<ans;//华丽结束！
return 0;
}