CF1824A LuoTianYi and the Show

题意

有 \(n\) 个人、编号为 \(1\) 至 \(m\) 的 \(m\) 个座位与三种坐座位的方式：

1. 坐在最左边的人的左边，当 \(1\) 号座位也不为空时就不坐了，当没有人坐在座位上时坐在 \(m\) 号座位上；
2. 坐在最右边的人的右边，当 \(m\) 号座位也不为空时就不坐了，当没有人坐在座位上时坐在 \(1\) 号座位上；
3. 坐在指定编号的座位上，当已经有人坐在这个座位上时就不坐了。

每个人都有一种坐座位的方式，你可以任意指定他们坐座位的顺序，问最多能坐多少个人。

\(n,m \le 2 \times 10^5\)。

思路

为了方便，我们将上边三种坐进去的方式所对应的三种人称为一类人、二类人与三类人。

首先我们先把三类人排个序去个重，这样至少每个三类人都有座位坐，于是我们先把他们安排进去再说。

然后对于一类人与二类人，可以任意指定一个三类人作为锚节点，在保证其他三类人也坐得进去的前提下尽量多的向其左右插入一类人与二类人。可以保证一定存在这样一种插入方式。于是我们可以 \(O(n)\) 预处理出每个三类人左右的空位，然后再扫一遍取得最大值。

还有一种情况就是，仍然在保证所有三类人都坐的进去的前提下，只安排一类人或二类人其中一种人的座位，这个可以特判一下。

代码

int n, m;
std::cin >> n >> m;

std::vector<int> x(n), a;
int lcnt = 0, rcnt = 0;
for (int i = 0; i < n; i++) {
  std::cin >> x[i];
  if (x[i] > 0) {
    a.push_back(x[i]);
  } else if (x[i] == -1) {
    lcnt++;
  } else if (x[i] == -2) {
    rcnt++;
  }
}

if (a.empty()) {
  std::cout << std::min(m, std::max(lcnt, rcnt)) << "\n";
  return;
}

std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
n = a.size();

std::vector<int> l(n), r(n);
int max = std::min(m - n, std::max(lcnt, rcnt));
for (int i = 0; i < n; i++) {
  l[i] = a[i] - i - 1;
  r[i] = m - a[i] - (n - i - 1);
  max = std::max(max, std::min(lcnt, l[i]) + std::min(rcnt, r[i]));
}

int ans = n + max;
std::cout << ans << "\n";