H. Sakurako's Test

原题

 本题通过前缀和和二分可以解决, 原理并不是很困难, 但是比较难想到

我们只需要对每一个 x, 二分求出中位数, 预处理好即可, 二分的检查通过求k倍的x可以在调和级数的时间内实现

代码

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 200010;int n, m, k, q, ans, x;void solve()
{cin >> n >> m;vector<int> a(n);vector<int> c(n + 1, 0ll);for (int i = 0; i < n; i ++ ){cin >> a[i];
//		记录每个数出现几次 c[a[i]] ++;}for (int i = 1; i <= n; i ++ ){
//		做前缀和 c[i] += c[i - 1];}int res[n + 1] = {0};for (int x = 1; x <= n; x ++ ){int l = 0, r = x;while (l < r){int mid = (l + r) / 2;int cnt = c[mid];
//			调和级数, x 越大此处用时越小 for (int k = 1; k * x <= n; k ++ ){cnt += c[min(k * x + mid, n)] - c[k * x - 1];}if (cnt - 1 >= n / 2){r = mid;}else{l = mid + 1;}}res[x] = l;}while (m -- ){int x;cin >> x;cout << res[x] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}