题解 P4801 【[CCO 2015]饥饿的狐狸】

· · 题解

这道题虽然没有用到什么很复杂的算法或数据结构，但是……

坑点很多！

PS:题解较长请耐心看完，讲的应该蛮详细了，至于中间一些吐槽……实在是因为做题过程中太辛酸了……如引起不适请忽略qwq

更好的阅读体验请戳我QAQ

【容许我扯皮一点东西】

我第一眼看过去，以为是一道贪心题，没有认真审题就三分钟交程序了……结果……

就出事了

找了半天才发现，并不是贪心题……漏看了一句话

吃饭就吃饭嘛干嘛先喝水啊qwq什么坏习惯

明白不能贪心以后，就开始了艰苦卓绝的思考。

好，那么接下来进入正题：

首先，哎，很容易就可以得出最小肥宅美味值的情况，就是在考虑喝水的情况下按照饼干温度依次吃下去（我最喜欢这种贪心思想了），就可以求出最小值了。我们先对可爱的小狐狸要吃的饼干进行排序，然后开始遍历从w到各点的距离，记得取绝对值！

我们可以画张图 （啊好丑啊qwq我尽力了相信我） 就是从w点出发依次遍历各点，得出最小值。

最小值解决完以后，就要解决恶心的最大美味值了……

最大值的求解方法有点类似于最优化问题，就是从温水煮青蛙开始，依次枚举左右，取能获取的最大美味值走，每次获得新状态前，都与喝水的情况做比较，取最优解，得出的答案即最大美味值。

然后又有一个要注意的地方了呢qwq

取得最小值的过程我之前想都不想就写了一个很朴素的函数来暴力求解。代码如下：

long long GetMin()
{
    long long MIN=0;
    long long mid;
    long long now=w;
    for (int i=1;i<=n;++i)
    {
        if ((a[i]<=w)&&(a[i+1]>=w))
        {
            mid=i;
        }
        if (a[i]>=w)
        {
            MIN+=abs(a[i]-now);
            now=a[i];
        }
    }
    now=w;
    for (int i=mid;i>=1;--i)
    {
        MIN+=abs(a[i]-now);
        now=a[i];
    }
    return MIN;
}

然后就……

后来又算来算去花了十分钟（其实花了一个多小时，我太弱了）

终于悟出最小值其实可以用O(1)的公式求解。代码如下：

long long GetMin()
{
    return max((long long)0,w-a[1])+max((long long)0,a[n]-w);
}

啊，好短，然而确实是正确的。

之后就是一些细节处理了，记得开long long。

上AC代码：

Code

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
long long w;//不开long long就凉凉 
long long a[1000010];
long long read()//读入优化 
{
    char chr;
    long long f=1;
    while (((chr=getchar())<'0')||(chr>'9'))
    {
        if (chr=='-')
        {
            f=-1;
        }
    }
    long long ans=chr-'0';
    while (((chr=getchar())>='0')&&(chr<='9'))
    {
        ans=ans*10+chr-'0';
    }
    return ans*f;
}
long long GetMin()
{
    return max((long long)0,w-a[1])+max((long long)0,a[n]-w);//是不是很奇妙的式子qwq 
}
long long GetMax(int check)//check表方向 
{
    int l=1,r=n;
    long long MAX=0;
    long long now=w;
    for (int i=1;i<=n;++i)
    {
        if (i%2==check)
        {
            MAX+=max(abs(a[l]-now),abs(a[l]-w));//往左找，记得取绝对值 
            now=a[l];
            l++;    
        }
        else
        {
            MAX+=max(abs(a[r]-now),abs(a[r]-w));//往右找 
            now=a[r];
            r--;
        }
    }
    return MAX;
}
int main()
{
    cin>>n;
    w=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
    }
    sort(a+1,a+n+1);//排序 
    long long minn=GetMin();//取最小值 
    long long maxn=max(GetMax(0),GetMax(1));//0表示向左找，1表示向右找 
    cout<<minn<<" "<<maxn<<"\n";
    return 0;
}

留个赞可好？qwq