[CSP2020]贪吃蛇 [贪心]

周末偷偷看了看CSP T4，发现非常刺激，铁牌退役狗想了一中午（不过感觉比树上的树简单不少）

注意到本题中的蛇只需要最大化自己吃几个，不需要最大化排名。我们称拥有其它蛇梦寐以求的选择权利的蛇为后浪蛇（当前值最大），没有选择权利的蛇为打工蛇（当前值最小）。

考虑后浪蛇的策略：如果吃掉打工蛇，在游戏之后一定不会死，那就吃，否则就不吃。于是只需要求会不会死。

可以发现吃掉打工蛇之后，如果自己没有变成打工蛇，那么它的值一定大于之后产生的所有新蛇，于是不会死可以吃。如果吃掉后只剩下自己，也可以吃。

如果后浪蛇吃掉打工蛇后自己变成打工蛇，那么它很可能被下一个吃掉。于是只需判断下一个后浪蛇是否可以吃掉它。如果吃掉当前打工蛇，下一个后浪蛇可以吃掉自己，那么就必须停止游戏。否则就可以吃。于是可以假装吃掉了打工蛇，把问题丢给下一个后浪，递归求解。递归边界是某条后浪吃掉打工蛇后自己没有变成打工蛇。

当然其实不需要递推，开个set模拟就行。注意到模拟上述过程时间不太够，考虑用某年noip蚯蚓那个题的经典方法优化。具体来说，开两个deque，由上面的分析可知产生的新蛇一定更小，于是把初始蛇丢尽第一个队列，新产生的蛇丢进第二个队列，假装它是个set就行了。

#include <bits/stdc++.h>
using std::cerr;
using std::endl;

inline int rd() {
  int b = 0; char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return b;
}

const int N = 1e6 + 233;

struct Node {
  int val, id;
  bool operator<(Node n) const {
    return val < n.val || (val == n.val && id < n.id);
  }
  bool operator==(Node n) const {
    return val == n.val && id == n.id;
  }
};

int ans, n, A[N];

inline void solve(int kase) {
  ans = rd();
  if (kase == 1) {
    n = ans;
    for (int i = 1; i <= n; ++i)
      A[i] = rd();
  } else {
    for (int i = 1; i <= ans; ++i) {
      int x = rd(), y = rd();
      A[x] = y;
    }
  }
  ans = n;
  std::deque<Node> que1, que2;
  for (int i = 1; i <= ans; ++i)
    que1.push_front({A[i], i});
  while (true) {
    if (que1.size() + que2.size() <= 2) {
      if (que1.size() + que2.size() == 2)
        --ans;
      break;
    }
    Node min, max;
    min = que1.back();
    que1.pop_back();
    if (que2.empty()) {
      max = que1.front();
      que1.pop_front();
    } else {
      if (que1.size() == 1 || que1.front() < que2.front()) {
        max = que2.front();
        que2.pop_front();
      } else {
        max = que1.front();
        que1.pop_front();
      }
    }
    max.val -= min.val;
    if (!que1.empty() && que1.back() < max) {
      que2.push_back(max);
      --ans;
      continue;
    }
    int del = 0;
    while (true) {
      if (que1.size() + que2.size() == 1)
        break;
      min = max;
      if (que2.empty()) {
        max = que1.front();
        que1.pop_front();
      } else {
        if (que1.size() == 1 || que1.front() < que2.front()) {
          max = que2.front();
          que2.pop_front();
        } else {
          max = que1.front();
          que1.pop_front();
        }
      }
      max.val -= min.val;
      if (!que1.empty() && que1.back() < max)
        break;
      if (!que2.empty() && que2.back() < max)
        break;
      del ^= 1;
    }
    ans -= del;
    break;
  }
  printf("%d\n", ans);
}

int main() {
  int T = rd();
  for (int i = 1; i <= T; ++i)
    solve(i);
  return 0;
}