CF1893C Freedom of Choice

· · 题解

CF1893C Freedom of Choice

首先算出 |X| 的上下界 [L, R]，由于不同的 a_{i, j} 的种类只有 N = \sum n 种，于是若 R - L + 1 > N，根据抽屉原理，总能找到 |X| \in [L, R] 使得 |X| 不等于任何 a_{i, j}，答案为 0。

于是 R - L + 1 \leq N，可以直接枚举 x = |X|。对第 i 个可重集，我们把不等于 x 的 a_{i, j} 全部选上，设总数为 s_i。如果 s_i < l_i，说明无论如何都要补充 l_i - s_i 个 x 加入 X，然后令 s_i \gets l_i。如果 s_i > r_i 则需要令 s_i\gets r_i。将 s_i 求和得到 S。

如果 S \geq x，说明可以丢掉若干个元素（但不能丢掉 x，因为这些 x 必须要加）使得 S = x。

如果 S < x，说明还要加入 x - S 个 x：如果还有不等于 x 的 a_{i, j} 没被选，那一定是因为 s_i > r_i 导致的，所以只有等于 x 的 a_{i, j} 能选，且就是因为没选 a_{i, j} = x 导致了 S < x。

这样可以算出 x = |X| 时 X 最少有多少个 x，将所有 x\in [L, R] 的答案取最小值即可。

为了避免复杂度退化为 \mathcal{O}(mN)，枚举 x 时需要快速知道有哪些 i 存在 j 使得 a_{i, j} = x，用 map<long long, vector<int>> 维护；以及对每个 i 和值 a_{i, j}，在 j 未知的情况下求出对应的 c_{i, j}，用 map<pair<int, long long>, long long> 维护。

时间复杂度线性对数。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd(1064);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

constexpr int mod = 998244353;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}

constexpr int Z = 1e6 + 5;
int fc[Z], ifc[Z];
int bin(int n, int m) {
  if(n < m) return 0;
  return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
void init_fac(int Z) {
  for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  ifc[Z - 1] = ksm(fc[Z - 1], mod - 2);
  for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
}

// ---------- templates above ----------

constexpr int N = 1e5 + 5;

ll m, n[N], l[N], r[N], sc[N];
vector<ll> c[N], a[N];
void mian() {
  cin >> m;
  ll suml = 0, sumr = 0, sumn = 0;
  map<ll, vector<int>> mp;
  map<pair<int, ll>, ll> mp2;
  for(int i = 1; i <= m; i++) {
    vector<ll> ().swap(c[i]);
    vector<ll> ().swap(a[i]);
    cin >> n[i] >> l[i] >> r[i], sc[i] = 0;
    sumn += n[i], suml += l[i], sumr += r[i];
    c[i].resize(n[i]);
    a[i].resize(n[i]);
    for(int j = 0; j < n[i]; j++) cin >> a[i][j], mp[a[i][j]].push_back(i);
    for(int j = 0; j < n[i]; j++) cin >> c[i][j], sc[i] += c[i][j];
    for(int j = 0; j < n[i]; j++) mp2[{i, a[i][j]}] = c[i][j];
  }
  if(sumn < sumr - suml + 1) {
    cout << 0 << "\n";
    return;
  }
  ll ans = LONG_LONG_MAX;
  for(ll cnt = suml; cnt <= sumr; cnt++) {
    ll tot = sumr, res = 0;
    vector<int> index = mp[cnt];
    for(int i : index) {
      tot -= r[i];
      ll ctr = sc[i] - mp2[{i, cnt}];
      if(ctr < l[i]) res += l[i] - ctr, ctr = l[i];
      tot += min(ctr, r[i]);
    }
    ans = min(ans, res + max(0ll, cnt - tot));
  }
  cout << ans << "\n";
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  while(T--) mian();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}