P3536 [POI2012]BON-Vouchers

Alex_Wei · 2021-12-19 22:33:57 · 题解

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;
}