题解 | 小苯的水果园

//思路;把每类出现的次数中相同的出现次数做累加，在用总的数减去小于等于次天数对应的和
//算法：哈希表+前缀和。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
ll a[N];
void solve(int sum, int q)
{
  //哈希表，时间复杂度O1；
  unordered_map<int, int> mp;
  for (int i = 1; i <= sum; i++)
  {
    int x;
    cin >> x;
    assert(x <= 1e6);
    mp[x]++;
  }
  //初始化元素值都为0动态数组。便于后续的前缀和的实现。
  vector<int> v(sum + 1, 0);
  for (auto&[x, y] :mp)
  {
    v[y] += y;
  }

  //前缀和的实现，时间复杂度为O1;
  for (int i = 1; i <= sum; i++)
  {
    v[i] += v[i - 1];
  }
  int t = sum;
  //q次询问
  while (q--)
  {
    int d;
    int remain;
    cin >> d;
    d = min(d, sum);
    remain = t - v[d];
    cout << remain << ' ';
  }
  //易犯格式化错误，每轮询问后要进行换行。
  cout << endl;
}
int main()
{
  //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int T;
  cin>>T;
  while(T--)
  {
    int n, q;
    cin >> n >> q;
    assert(n <= 2e5);
    assert(n <= 2e5);
    solve(n, q);
  }
  return 0;
}