LOJ #3834. 「IOI2022」最罕见的昆虫 题解

Description

Pak Blangkon 的房子四周有 $N$ 只昆虫，编号为 $0$ 至 $N-1$。每只昆虫有一个类型，以从 $0$ 至 $10^9$（包含 $0$ 和 $10^9$）的整数编号。可能有多只昆虫类型相同。

假设将昆虫按照类型分组。我们定义最常见昆虫类型的基数是昆虫最多的分组中的昆虫数。类似地，最罕见昆虫类型的基数是昆虫最少的分组中的昆虫数。

例如，假设有 $11$ 只昆虫，类型分别为 $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$。在此情形中，最常见昆虫类型的基数是 $3$，是因为类型 $9$ 和类型 $11$ 的分组均有最多数目的昆虫，每个分组都有 $3$ 只。最罕见昆虫类型的基数是 $1$，是因为类型 $7$、类型 $0$ 和类型 $100$ 的分组均有最少数目的昆虫，每个分组都有 $1$ 只。

Pak Blangkon 不知道这些昆虫的类型。他有一台单按钮的机器，可以提供昆虫类型相关的信息。刚开始时，机器是空的。在使用机器时，可以做如下三种操作：

1. 将一只昆虫放进机器。
2. 将一只昆虫取出机器。
3. 按下机器的按钮。

每当按下按钮时，机器会报告在机器内的最常见昆虫类型的基数。

你的任务是使用上述机器，确定 Pak Blangkon 的房子四周所有 $N$ 只昆虫中最罕见昆虫类型的基数。此外，在某些子任务里，你的得分取决于机器执行某种操作的最大次数（详见子任务一节）。

每种操作最多可以做 $3N$ 次。

Solution

由于交互过程中的查询是查询众数，而要求出全局出现次数最少的次数，这个是比较矛盾的两个东西，是不好直接做的。

考虑二分。现在问题变为给定一些数，怎么判断它们出现最少的次数 $\geq k$。

首先我们可以通过依次往里面加数，如果最少次数超过 $1$ 就删掉当前数的方式求出总颜色数量 $c$。

二分的判断等价于是判断可不可以存在一个局面使得每种颜色出现恰好 $k$ 次，我们可以通过限制众数的方式让每种颜色出现次数不超过 $k$。如果加进机器中的元素数量达到 $c\times k$ 就说明判断成功。

直接做是 $O(n\log n)$ 次操作，不太能过。

---

考虑优化。

上面的做法劣是因为每次判断都是重新做，没有用上之前二分的过程中得到的信息。

设当前的二分区间是 $[L,R]$，表示答案在 $[L,R]$ 范围内。我们钦定 check 之前机器中每个颜色都有 $L$ 个，同时也知道可以加入机器的 $c\times(R-L)$ 个元素。

然后二分 $mid$，一个一个往里面加，保证任意时刻众数不超过 $mid+1$。

如果 $mid+1$ 判断成功了，就说明区间会变为 $[mid+1,R]$，且可加入机器的元素为这次二分时加入失败的元素。如果判断失败，则先会退到初始状态，可加入机器的元素变为这次二分时加入成功的元素。

由于每次二分区间长度都会减半，所以二分的总次数为 $T(n)=T(n/2)+n=2n$，加上求颜色数的 $n$ 次就恰好为 $3n$ 次。

但是直接做是会比 $3n$ 多一点的，注意到在二分的过程中 $mid$ 多增加一点，单次二分会多出一些次数，所以在区间长度超过 $5$ 的时候让原先的 $mid$ 减少 $1$ 即可通过。

Code

#include "insects.h"
#include <bits/stdc++.h>

const int kMaxN = 2e3 + 5;

int n, cnt;
bool vis[kMaxN], in[kMaxN];

void add(int x) { move_inside(x - 1), vis[x] = 1, ++cnt; }
void del(int x) { move_outside(x - 1), vis[x] = 0, --cnt; }
int qry() { return press_button(); }

int getcnt() {
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    add(i), in[i] = 0;
    if (qry() > 1) del(i), in[i] = 1;
    else ++cnt;
  }
  return cnt;
}

int min_cardinality(int N) {
  n = N, cnt = 0;
  int c = getcnt(), L = 1, R = n / c;
  while (L < R) {
    assert(cnt == L * c);
    int mid = (L + R) >> 1;
    if (R - L >= 5) --mid;
    std::vector<int> tmp1, tmp2;
    for (int i = 1; i <= n; ++i) {
      if (in[i]) {
        add(i);
        if (qry() > mid + 1) del(i), tmp1.emplace_back(i);
        else tmp2.emplace_back(i);
      }
      if (cnt == c * (mid + 1)) break;
    }
    if (cnt == c * (mid + 1)) {
      L = mid + 1;
      for (auto x : tmp2) in[x] = 0;
    } else {
      R = mid;
      for (auto x : tmp1) in[x] = 0;
      for (auto x : tmp2) del(x);
    }
  }
  return L;
}