嗨嗨嗨

全部评论 2

• 

  应昕成

  

  删除

  很好，你提出了一个非常典型的信奥竞赛题目——它结合了贪心策略、模拟过程、数据结构优化以及对博弈逻辑的深刻理解。我们来一步步引导你思考这个问题。

  🌟 第一步：理解题意是关键
  首先，我们要彻底搞清楚每条蛇的行为逻辑：

  每一轮：
  找出当前“最强”的蛇（按规则：体力值大者胜；相等时编号大者胜）。
  找出当前“最弱”的蛇（同理比较）。
  最强的蛇有选择权：吃 or 不吃？
  如果吃 → 它的体力减少（变为 a_x - a_y），被吃的蛇退出。
  如果不吃 → 游戏立刻结束。
  所有蛇都非常聪明，并且目标是：
  在自己不被吃掉的前提下，尽可能多地吃别的蛇。

  注意这个目标不是“活到最后”，而是：“只要我不死，我就想多吃”。但前提是不能让自己陷入将来被别人吃掉的境地。

  🔍 第二步：从样例入手，模拟思维
  让我们先看第一个样例：

  初始：n=3, a = [11, 14, 14] （编号1:11, 2:14, 3:14）
  谁最强？谁最弱？
  最强：比较 (14,2) 和 (14,3)，因为值相同，编号大的赢 → 3号最强
  最弱：1号（11）
  所以第一轮：3号决定是否吃1号。

  如果 3号吃1号：

  3号新体力 = 14 - 11 = 3
  剩下蛇：2号(14), 3号(3)
  下一轮：最强的是2号（14），最弱的是3号（3）
  此时2号可以选择吃3号（因为它不怕被反杀，只剩它一个了）
  结果：3号被吃 → 3号死了！
  而3号的目标是“不被吃的情况下多吃”，但现在吃了反而导致 得不偿失。

  所以，3号会选择不吃 → 决斗结束 → 三条都活着。

  ✅ 输出 3

  再看修改后的情况：

  a = [5, 6, 25]
  最强：3号（25）
  最弱：1号（5）
  若3号吃1号 → 新体力 = 20，剩下：2号(6), 3号(20)

  下一轮：

  最强：3号（20）
  最弱：2号（6）
  → 3号可以继续吃，变成 14
  然后只剩自己 → 安全

  所以3号吃了两个，全程不会被吃 → 利益最大化 → 会吃！

  最终只剩1条 → 输出 1

  ❓ 关键问题浮现：
  一条蛇在考虑要不要吃的时候，必须预判：吃完之后，我有没有可能在未来某一轮被别人吃掉？

  但如果每次都完整模拟整个后续流程，复杂度太高（尤其是 n 达到 1e6）。

  所以我们需要寻找规律或性质！

  💡 第三步：提出几个启发式问题，帮你深入思考
  你可以试着回答以下几个问题，核心思想：

  什么情况下最强蛇会选择“不吃”？

  是不是当它吃了之后，会导致自己变得太弱，从而在后续轮次中成为“可被吃”的对象？
  那么，“安全”意味着什么？是否存在一种状态，让某条蛇一旦达到就可以无惧地继续吃下去？
  假设只剩下两条蛇，会发生什么？

  强者一定吃弱者吗？还是也可能不吃？
  -之后就没了对手，不会再被吃 → 所以它一定会吃！
  所以两蛇局面 →一条
  再往前推一步：三条蛇时，最强蛇会不会吃？

  吃完后变成两条蛇的局面 → 对方将成为唯一的竞争者
  若我能打赢那条蛇（即吃完最弱后，我的体力 ≥ 对手），那我可以安全地继续吃
  否则，我变弱了，对方会吃我 → 我就不吃
  这像不像一种 倒推决策 的过程？

  能不能用栈或者队列来维护候选蛇？

  想象一下：每次最强蛇吃最弱蛇，相当于最大值减去最小值，然后放回集合
  这个操作很像“石子合并”类在于：蛇是否愿意执行这个操作取决于未来风险
  有没有可能使用类似“单调栈”或“双端队列”的结构来高效处理？
  观察数据范围提示：保证修改后的数组是非降序排列的

  这个条件非常重要！说明我们可以利用有序性进行优化
  是否可以考虑将蛇按体力从小到大排序（同时记录编号）？
  然后用某种方式模拟“强者吞并弱者”的连锁反应？
  有没有可能出现循环或多轮吞噬？比如强者吃弱者后仍为强者，接着吃下一个最弱？

  是的！就像第二个样例那样，3号连续吃了两个
  所以如果一条蛇足够强，它可以一路吃到底 → 直到只剩自己
  这种蛇我们称之为“稳定统治者”？
  什么样的蛇能成为“稳定统治者”？

  它的体力必须大于等于其余所有蛇体力之和吗？
  比如：总和为 S，它为 X，X > S？不一定，因为每次只减一点点
  但反过来想：如果它的体力小于剩余蛇的总和，是否一定无法安全吃完？
  或者更精细一点：是否存在一个阈值，使得一旦满足就能安全吞并所有小蛇？
  🧩 第四步：尝试抽象模型
  考虑如下建模：

  维护一个有序集合（比如 multiset 或优先队列），支持快速取出最大和最小元素
  但是不能盲目模拟每一轮，因为最坏情况可能会有 O(n) 轮，每轮 O(log n)，总共 O(n log n)，对于 1e6 可能勉强卡过（但 T≤10，k≤1e5，还要处理多组数据）
  更重要的是：并不是所有蛇都会参与实际决斗！
  重点来了：

  很多时候，最强蛇一看形势不利，直接选择“不吃”，游戏结束。

  所以真正

  1周前 来自 浙江

  0
• 

  zyy

  删除

  #include <bits/stdc++.h>
  #define fo(a,b,c) for (a=b; a<=c; a++)
  #define fd(a,b,c) for (a=b; a>=c; a--)
  #define ll long long
  #define file
  using namespace std;
  struct type
  {
  int s,x;
  } s1,s2;
  struct Queue
  {
  type d[1000001];
  int h,t;
  void push(type s)
  {
  d[++t] = s;
  }
  void pop(bool tp)
  {
  if (!tp)
  {
  ++h;
  }
  else
  {
  --t;
  }
  }
  void clear()
  {
  h = 1,t = 0;
  }
  bool empty()
  {
  return h > t;
  }
  type head()
  {
  return d[h];
  }
  type tail()
  {
  return d[t];
  }
  } q[2];
  int a[1000001],T,n,i,j,k,l,I,x,y,ans,I1,I2,sum;
  bool operator < (type a,type b)
  {
  return a.s < b.s || a.s == b.s && a.x < b.x;
  }
  bool operator > (type a,type b)
  {
  return a.s > b.s || a.s == b.s && a.x > b.x;
  }
  void swap(int &x,int &y)
  {
  int z = x;x = y;y = z;
  }
  int main(void)
  {
  scanf("%d",&T);
  fo(I,1,T)
  {
  if (I == 1)
  {
  scanf("%d",&n);
  fo(i,1,n) scanf("%d",&a[i]);
  }
  else
  {
  scanf("%d",&k);
  fo(i,1,k) scanf("%d%d",&x,&y),a[x] = y;
  }
  q[0].clear(),q[1].clear(),ans = n;
  I1 = 0,I2 = 1;
  fd(i,n,1) q[I1].push(type{a[i],i});
  while (ans > 1)
  {
  --ans;
  if (q[I2].empty() || q[I1].tail() < q[I2].tail())
  {
  s2 = q[I1].tail(),q[I1].pop(1);
  }
  else
  {
  s2 = q[I2].tail(),q[I2].pop(1);
  }
  if (!s2.s)
  {
  continue;
  }
  if (q[I2].empty() || q[I1].head() > q[I2].head())
  {
  s1 = q[I1].head(),q[I1].pop(0);
  }
  else
  {
  s1 = q[I2].head(),q[I2].pop(0);
  }
  s1.s -= s2.s;
  if (q[I1].empty())
  {
  swap(I1,I2);
  }
  q[I2].push(s1);
  if (q[I1].tail() > s1)
  {
  break;
  }
  }
  if (ans > 1)
  {
  sum = 0;
  while (sum < ans - 1)
  {
  if (q[I2].empty() || q[I1].tail() < q[I2].tail())
  {
  s2 = q[I1].tail(),q[I1].pop(1);
  }
  else
  {
  s2 = q[I2].tail(),q[I2].pop(1);
  }
  if (q[I2].empty() || q[I1].head() > q[I2].head())
  {
  s1 = q[I1].head(),q[I1].pop(0);
  }
  else
  {
  s1 = q[I2].head(),q[I2].pop(0);
  }
  s1.s -= s2.s;
  if (q[I1].empty())
  {
  swap(I1,I2);
  }
  if (!q[I1].empty() && q[I1].tail() < s1 || !q[I2].empty() && q[I2].tail() < s1)
  {
  break;
  }
  q[I2].push(s1);
  ++sum;
  }
  sum += sum == (ans - 1);
  ans += !(sum&1);
  }
  printf("%d\n",ans);
  }
  fclose(stdin);
  fclose(stdout);
  }

  2024-12-03 来自 北京

  0