P7078 贪吃蛇（贪心+单调性优化）

木xx木大 · 2020-11-18 18:44:34 · 题解

P7078 贪吃蛇

比赛时能做出来这题的都是神仙，因为他和蛇一样聪明！ 本篇题解的主要思路是参考sll学长的视频讲解的，在这里orz！

设所有蛇的实力为 a_1,a_2\dots a_n ，a_1 最小， a_n 最大。下面我们分情况讨论最大的蛇是否选择吃：

Case1：当前最强的蛇吃了最弱的蛇之后没有变成最弱的蛇

（结论一）如果当前最强的蛇吃了最弱的蛇之后没有变成最弱的蛇，它一定会选择吃！证明如下：

• 如果它吃完以后仍然是最大的蛇，不吃白不吃
• 否则，下一个最大的蛇为 a_{n-1}，下一个最小的蛇为 a_2。因为 a_n\geq a_{n-1}，a_2\geq a_1 ，所以 a_n-a_1\geq a_{n-1}-a_2 。如果 a_{n-1} 选择吃，那么它吃完后会比 a_n 吃完后更小，也就是说，它如果死也会死在 a_n 之前，由于它会尽量不死，所以 a_n 也不会死；如果 a_{n-1} 选择不吃，那么决斗结束， a_n 仍然安全。

Case2：当前最强的蛇吃了最弱的蛇之后变成了最弱的蛇

显然(废话) ，如果它吃完以后，在之后的决斗中不会死，它就吃；换句话说，（结论二）在轮到它死之前，已经有蛇选择结束决斗，它就吃。

根据以上两个结论，我们可以得到本题的基本思路：

步骤一 ：我们先不考虑 Case2，假设所有的蛇都不聪明，按照 Case1 进行正向模拟一遍，记录每一轮中吃的蛇和被吃的蛇（即最大值 mx_i 和最小值 mi_i）。显然的做法是用 set 维护。

步骤二：再考虑 Case2。记 dead_i 表示第 i 条蛇死的时间。从后往前，替每一轮中的蛇决定它是否要吃。从后往前是因为每条蛇当前是否选择结束游戏，是要根据它之后是否被吃判断的（结论二）。记 ans 表示决斗会在哪一轮结束。如果 dead_{mx_i}<ans ，那么结束，ans=i。最终答案即为 n-ans+1 。

以上做法的复杂度瓶颈在于步骤一的模拟中需要用到 set ，每次取出最大最小值复杂度为 O(\log n) ，我们希望把这一操作的复杂度降为 O(1)。看到题目中说保证每组数据（包括所有修改完成后的）的 a_i 以不降顺序排列，我们考虑用队列代替 set 维护，重新思考 Case1 和 Case2 中隐含的单调性。

设 w=a_n-a_1。我们维护两个队列， q1 中存原来的蛇，q2 中存每次新得到的蛇。

Case1：如果 w>a_{n-1}，那么下一次的最大值为 w ，w-a_2<w；否则w>a_{n-1}-a_2 。满足单调性。（其实就是上面对结论一的证明）

Case2： w 就是下一次被吃掉的蛇。所以队列中始终只有一个元素，显然满足单调性。

根据上面的分析， 如果只有 Case1 或 Case2 ， q2 都是单调的。但如果 Case1 和 Case2 交替出现呢？

• 如果一串 Case1 后跟一串 Case2 ，Case2 会反复进出队，队里以前的元素不会用到
• 如果一串 Case2 后遇到一个 Case1，确实可能会不满足单调性。但是！这次的 Case1 被吃掉的是上次 Case2 中选择吃蛇的蛇，既然它这次被吃了，那么因为它足够聪明，它上一次就不会选择吃！也就是说，这是一个边界条件，决斗在这之前就结束啦！因此，不满足单调性也是没有关系的。

综上：q1 和 q2 都是满足单调性的。所以我们可以用两个 deque 代替 set，复杂度就降为 O(Tn) 了。具体实现细节可以看代码。

这道题我从学习解法，写代码，到写完这篇题解，花了整整一下午时间。这也是我写过的最长且最详细的一篇题解。希望大家和以后再回来看这篇题解的我都能看懂吧。

#include<bits/stdc++.h>
#define inl inline
using namespace std;
namespace FGF
{
    int n,m;
    const int N=1e6+5;
    int b[N],a[N],q[N],de[N],h,t,st,ed,fl,end;
    struct Node{
        int mx,mi;
        Node(){};
        Node(int _mx,int _mi):mx(_mx),mi(_mi){};
    }c[N];
    int read()
    {
        int s=0;char ch=getchar();
        while(!isdigit(ch))ch=getchar();
        while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
        return s;
    }
    inl int getcm()//查找次小值 
    {
        int mi;
        if(st>ed)mi=q[t];
        else if(h>t)mi=st;
        else if(a[st]<a[q[t]]||(a[st]==a[q[t]]&&st<q[t]))mi=st;
        else mi=q[t];
        return mi;
    }
    inl int getmi()//取出最小值 
    {
        int mi;
        if(st>ed)mi=q[t],t--;
        else if(h>t)mi=st,st++;
        else if(a[st]<a[q[t]]||(a[st]==a[q[t]]&&st<q[t]))mi=st,st++;
        else mi=q[t],t--;
        return mi;
    }
    inl int getmx()//取出最大值 
    {
        int mx;
        if(st>ed)mx=q[h],h++;
        else if(h>t)mx=ed,ed--;
        else if(a[ed]>a[q[h]]||(a[ed]==a[q[h]]&&ed>q[h]))mx=ed,ed--;
        else mx=q[h],h++;
        return mx;
    }
    void solve()
    {//这里我直接将a数组当q1用了 
        h=1,t=0,st=1,ed=n,fl=0,end=n-1;
        for(int i=1;i<n;i++)//决斗最多进行n-1轮 
        {
            int mx=getmx(),mi=getmi(),cm=getcm();
            a[mx]-=a[mi];
            q[++t]=mx;//把新得到的值放入q2 
            c[i].mx=mx,c[i].mi=mi;
            if(a[mx]>a[cm]||(a[mx]==a[cm]&&mx>cm))
            {
                if(fl)//一串Case2后跟了一个Case1，决斗结束 
                {
                    end=i;
                    break;
                }
            }
            else fl=i;//记录一下Case2出现过了 
        }
        for(int i=1;i<=n;i++)de[i]=end+1;//初始化dead数组 
        de[c[end].mi]=end;
        int ans=end+1;
        for(int i=end-1;i;i--)
        {
            if(de[c[i].mx]<ans)ans=i;
            de[c[i].mi]=i;
        }
        printf("%d\n",n-ans+1);
    }
    void work()
    {
        int T=read();n=read();
        for(int i=1;i<=n;i++)
            b[i]=a[i]=read();
        solve();
        for(int i=2;i<=T;i++)
        {
            int k=read();
            for(int j=1;j<=n;j++)a[j]=b[j];
            for(int j=1;j<=k;j++)
            {
                int x=read(),y=read();
                b[x]=a[x]=y;
            }
            solve();
        }
    }
}
int main()
{
    FGF::work();
    return 0;
}