这里，先放一个我做的 PPT：link。如果有补充，放在下面。
完整代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
typedef long long ll;
const ll N=1000000+10;
struct Snakes//使用运算符重载，可以方便地进行“蛇”运算。
{ //有题解使用 pair。这种东西是将两个数据合并到一块，两者数据类型不必相同。
ll id,hp;//蛇的体力，编号。
bool operator>(Snakes b)//定义蛇的大小。
{
if(this->hp==b.hp) return this->id>b.id;
return this->hp>b.hp;//this 是一个结构体指针，指向左值的地址。访问结构体成员的值使用 -> 运算符。
}
bool operator<(Snakes b)
{
if(this->hp==b.hp) return this->id<b.id;
return this->hp<b.hp;
}
Snakes operator-(Snakes b)//定义蛇的“吃”运算。
{
Snakes _t=*this;//!!! 40->100 qwq
_t.hp=this->hp-b.hp;
return _t;
}
}s[N];
ll n,ans=0;
deque<Snakes>q1,q2;//q1 是初始队列，q2 是吃了之后的队列（单调不升）
/* deque 的用法
q.front() 返回队首元素。
q.back() 返回队尾元素。
q.pop_front() 返回队首元素。
q.pop_back() 返回队尾元素。
q.push_front(x) 从队首压入元素 x。
q.push_back(x) 从队尾压入元素 x。
q.size() 返回队列大小。
q.clear() 清空队列。
*/
void init()
{
q1.clear();q2.clear();
for(ll i=1;i<=n;i++)
q1.push_front(s[i]);
}
Snakes getF()//取最大。
{
Snakes S;
if(q2.empty() ||//最开始，q2 为空，此时 q1 一定不为空。所以只能选择 q1.
(!q1.empty()&&//首先保证 q1 不为空。
q1.front()>q2.front()))//再保证 q1 比 q2 大。
S=q1.front(),q1.pop_front();
else S=q2.front(),q2.pop_front();//否则是 q2。
return S;
}
Snakes getB()//取 q1 最小。
{
Snakes S=q1.back();
q1.pop_back();
return S;
}
Snakes Check()//检查是否为最弱蛇。
{
Snakes S;
if(!q1.empty()) S=q1.back();
if(!q2.empty()&&S>q2.back()) S=q2.back();
return S;
}
void solve()
{
/* 思路：
将整场决斗分为两个阶段。
有一个显然的结论：当前最强的蛇如果吃了最弱的蛇之后，没有变成最弱的蛇，它一定会选择吃。
引理 1：如果蛇们按照规则一直吃，则吃完后的蛇是越来越弱的。
即，若 a_i 比 a_j 先吃，则 a_i > a_j。
证明 引理 1：最强蛇一定不如以前强，最弱蛇一定不如以前弱。
证明 显然的结论：它如果吃了，仍最强，不吃白不吃；
它如果吃了，不是最强的，则根据引理 1，之后的蛇吃后，一定比它要弱，一定会想尽办法不死。
因此不管如何，它一定死不了。
把 当前最强的蛇吃了最弱的蛇之后没有变成最弱的蛇 这个阶段，定为第一阶段。
然而，可能当前最强的蛇吃了最弱的蛇之后，变成了最弱的蛇！这时候，它吃不吃，取决于后面的蛇是否吃。
推理一下：
- 如果 a_i 吃了，变成最弱蛇，而 a_j 再吃 a_i 后不是最弱蛇，则 a_j 一定吃，那 a_i 就死了，所以 a_i 不能吃。
- 如果 a_i 吃了，变成最弱蛇，而 a_j 再吃 a_i 后是最弱蛇，而 a_k 吃了 a_j 不是最弱蛇，则 a_k 一定吃，
那 a_j 就死了，所以 a_j 不能吃。所以 a_i 能吃。
- 吃吃吃，如果最后场上只有两条蛇，则 a_i 无论如何都要吃。
把 当前最强的蛇吃了最弱的蛇之后都变成最弱的蛇 这个阶段，定为第二阶段。
所以这个问题就变成了一个递归的问题，边界是一条蛇打破了第二阶段或场上只有两条蛇了。
实际上，在程序设计时，不用写递归，因为注意到 a_i 能不能吃和递归层数的奇偶性有关。所以只需一个 while 即可解决。
*/
/* 程序设计：
定义双端队列 q1，q2。我们根据引理 1 找到了单调性，所以不用带 log 的数据结构维护。
第一阶段：
设 G 要吃 L，变成 T。之后把 T 压入 q2 尾部。
q2 队列中的蛇在第一阶段一定不会被吃（如果被吃，则说明上一个 G 变成了最弱蛇，进入第二阶段）。
第二阶段：
只需维护一个最弱蛇，不用再压入队列，因为第二阶段结束后整个决斗就停止了。并统计吃的次数。
这个阶段用来看能不能再吃一次。
*/
while(true)
{
ll cnt=0;//吃的次数
if(q1.size()+q2.size()<=2) {ans=1;return;}
Snakes L=getB(),G=getF();
Snakes T=(G-L);
if(T<q1.back() || q1.empty())//T == L
{
ans=q1.size()+q2.size()+2;//答案不必动态统计。
while(true)
{
cnt++;
if(q1.size()+q2.size()+1<=2){ans-=(cnt%2==0);/*奇偶性*/return;}
G=getF();T=(G-T);
if(T>Check()){ans-=(cnt%2==0);return;}
}
}else q2.push_back(T);
}
}
void yzmain()
{
ll T,t1,t2,k;
scanf("%lld",&T);
for(ll qwq=1;qwq<=T;qwq++)
{
if(qwq==1)
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&s[i].hp);
s[i].id=i;
}
}
else
{
scanf("%lld",&k);
for(ll i=1;i<=k;i++)
{
scanf("%lld%lld",&t1,&t2);
s[t1].hp=t2;
}
}
init();
solve();
printf("%lld\n",ans);
}
return;
}
}
int main()
{
//freopen("snakes.in","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
无注释版
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
typedef long long ll;
const ll N=1000000+10;
struct Snakes
{
ll id,hp;
bool operator>(Snakes b)
{
if(this->hp==b.hp) return this->id>b.id;
return this->hp>b.hp;
}
bool operator<(Snakes b)
{
if(this->hp==b.hp) return this->id<b.id;
return this->hp<b.hp;
}
Snakes operator-(Snakes b)
{
Snakes _t=*this;
_t.hp=this->hp-b.hp;
return _t;
}
}s[N];
ll n,ans=0;
deque<Snakes>q1,q2;
void init()
{
q1.clear();q2.clear();
for(ll i=1;i<=n;i++)
q1.push_front(s[i]);
}
Snakes getF()
{
Snakes S;
if(q2.empty() || (!q1.empty()&&q1.front()>q2.front()))
S=q1.front(),q1.pop_front();
else S=q2.front(),q2.pop_front();
return S;
}
Snakes getB()
{
Snakes S=q1.back();
q1.pop_back();
return S;
}
Snakes Check()
{
Snakes S;
if(!q1.empty()) S=q1.back();
if(!q2.empty()&&S>q2.back()) S=q2.back();
return S;
}
void solve()
{
while(true)
{
ll cnt=0;
if(q1.size()+q2.size()<=2) {ans=1;return;}
Snakes L=getB(),G=getF();
Snakes T=(G-L);
if(T<q1.back() || q1.empty())
{
ans=q1.size()+q2.size()+2;
while(true)
{
cnt++;
if(q1.size()+q2.size()+1<=2){ans-=(cnt%2==0);return;}
G=getF();T=(G-T);
if(T>Check()){ans-=(cnt%2==0);return;}
}
}else q2.push_back(T);
}
}
void yzmain()
{
ll T,t1,t2,k;
scanf("%lld",&T);
for(ll qwq=1;qwq<=T;qwq++)
{
if(qwq==1)
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&s[i].hp);
s[i].id=i;
}
}
else
{
scanf("%lld",&k);
for(ll i=1;i<=k;i++)
{
scanf("%lld%lld",&t1,&t2);
s[t1].hp=t2;
}
}
init();
solve();
printf("%lld\n",ans);
}
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
本文作者：Yurchiu,zzy
本文链接：https://yz-hs.github.io/b1c1608155d2/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
