P3536 [POI2012]BON-Vouchers

POI 合集。

注意到对于一个固定的 $x$，我们只关心前 $\dfrac {\max b_i}x$ 个需求为 $x$ 的顾客，便可断言接下来需求为 $x$ 的顾客不可能拿到代金券，这一点显然。

因此，若当前需求为 $x$ 的顾客数量 $c_x>\dfrac{\max b_i}x$，那么可以跳过剩下来所有这样的顾客。直接暴力模拟，时间复杂度是调和级数求和产生的 $\mathcal{O}(b\ln b)$，可以接受。

const int N = 1e6 + 5;
int n, m, cnt, buc[N];
ll tot, ans[N], cur[N];
int main(){
	cin >> m;
	for(int i = 1; i <= m; i++) buc[read()] = 1;
	n = read();
	for(int i = 1; i <= n; i++) {
		int k = read();
		if(cur[k] * k >= N) {tot += k; continue;}
		int rest = k;
		while(rest) {
			int p = (++cur[k]) * k;
			if(p >= N) break;
			if(buc[p] == 1) ans[++cnt] = tot + k - rest + 1;
			if(buc[p] >= 0) buc[p] = -1, rest--;
		} tot += k;
	} cout << cnt << endl;
	for(int i = 1; i <= cnt; i++) print(ans[i]), pc('\n');
	return 0;
}