P7078 [CSP-S2020] 贪吃蛇 题解

· · 个人记录

难度：\color{black}\text{NOI/NOI+/CTSC}

\color{green}\text{AC算法：}贪心，队列

题目分析：

题面不用解释,就是让回答有多少蛇将存活。

显然，蛇保命的优先级最高，在自身能保命的前提下尽可能多的弄死别的蛇 （让我想起了海盗分金问题）

设当前蛇为 dq

可以分两种情况讨论：
1、 dq 吃了最弱的蛇之后不会变成最弱的蛇
2、 dq 吃了最弱的蛇之后会变成最弱的蛇

对于情况一：
显然可以大胆吃

对于情况二：
设 dq 进食后，新的老大为 dq2。此时 dq2也遇到了相同两种情况。如果 dq2 进食之后不会变成最弱的蛇，那么 dq2 一定会吃掉 dq，dq 不应该进食。如果 dq2 进食之后会变成最弱的，那么那就再看 dq3 的情况........就这样递归下去。直到有一条蛇可以吃或者只剩下两条蛇。此时设第 i 个蛇可以放心吃。那么第 i-1 条蛇就不应该吃，否则将在下一轮被吃掉。而第 i-2 条蛇可以吃，因为它知道第 i-1 条蛇不敢吃它。
现在就有了一个结论：对于第 i 轮递归的蛇可以大胆吃，如果 i 为奇数，那么当前蛇就不应该吃；如果 i 为偶数，那么当前蛇就可以大胆吃，然后转化为 i 为奇数的稳定状态。（当然如果只有两条蛇那么只有一条蛇可以存活）

题目分析完毕，剩余的在注释里。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
#define reg register
int a[maxn];
int t;
int n;
int k;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-1;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int main()
{
    t=read();
    int testcnt=0;
    while(t--)
    {
        testcnt++;
        int ans=0;
        if(testcnt==1)
        {
            n=read();
            for(reg int i=1;i<=n;i++)
            {
                a[i]=read();
            }
        }
        if(testcnt>1)
        {
            k=read();
            reg int x,y;
            for(reg int i=1;i<=k;i++)
            {
                x=read();
                y=read();
                a[x]=y;
            }
        }
        deque<pair<int,int> > que1;
        deque<pair<int,int> > que2;
        for(reg int i=1;i<=n;i++)
        {
            que1.emplace_back(make_pair(a[i],i));
        }
        while(1)
        {
            if(que1.size()+que2.size()==2)
            {
                ans=1;
                break;
            }
            //取出最弱
            int y=que1.front().first;
            que1.pop_front();
            //取出最强
            int x;
            int bianhao;//最强者编号
            if(que2.empty()||(!que1.empty()&&que1.back()>que2.back()))
            {//如果que1不空且它的最后一个元素是两个队列最大的才行
            //但是如果que2没有就只能选que1
                x=que1.back().first;
                bianhao=que1.back().second;
                que1.pop_back();
            }
            else{
                x=que2.back().first;
                bianhao=que2.back().second;
                que2.pop_back();
            }
            pair<int,int> xianzai=make_pair(x-y,bianhao);
            if(que1.empty()||xianzai<=que1.front())//pair自动比较第一个参数
            {//最强蛇进食之后变成了最弱蛇
                ans=que1.size()+que2.size()+2;
                //先假设不吃
                int count=0;
                //第几轮递归
                while(1)
                {
                    count++;
                    if(que1.size()+que2.size()+1==2)
                    {
                        if(!(count&1))ans--;
                        //可以发现，当轮数为偶数时，当前最强才能放心吃
                        break;
                    }
                    //重新选择当前最强递归下去
                    if(que2.empty()||!que1.empty()&&que1.back()>que2.back())
                    {   //如果que1不空且它的最后一个元素是两个队列最大的才行
                        //但是如果que2没有就只能选que1
                        x=que1.back().first;
                        bianhao=que1.back().second;
                        que1.pop_back();
                    }
                    else{
                        x=que2.back().first;
                        bianhao=que2.back().second;
                        que2.pop_back();
                    }
                    xianzai=make_pair(x-xianzai.first,bianhao);//之前的最强已经是最弱了，让现在的最强进食
                    if(!((que1.empty()||xianzai<que1.front())&&(que2.empty()||xianzai<que2.front())))
                    {//如果不是最弱的，那么看看能不能吃
                        if(!(count&1))
                        {
                            ans--;
                        }
                        break;
                    }
                }
                break;
            }
            else
            {
                que2.emplace_front(xianzai);
                //如果吃掉后不是最弱，那么大胆吃！
            }
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}