自动搬运

查看原文

来自洛谷，原作者为

	jiangly 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:04:37，当前版本为作者最后更新于2020-09-17 16:06:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先二分求出每个人结束的时间 $end_i$。

我们只需要求出每个人最后一次检票开始之后有多少次检票。即有多少个 $end_j-k\cdot a_j$ 大于等于 $end_i-a_i$，如果 $j\le i$ 则不能取等。

因为 $a_i$ 互不相同，且 $\max\{end_i\}-\min\{end_i-a_i\}\le 2C$ ($C=\max\{a_i\}$)，因此有用的数的个数只有 $O(C\log k)$。

我们记录每个数的出现次数，求后缀和求能得到所有 $\ge end_i-a_i$ 的数的个数。再减去 $i$ 之前出现的等于 $end_i-a_i$ 的数的个数即可。

时间复杂度 $O(k\log nC+C\log k)$。

#include <bits/stdc++.h>

constexpr int N = 1e5;

int64_t n;
int k;
int a[N];

int64_t pos[N];

int cnt[2 * N], ans[N];

int64_t count(int64_t m) {
    int64_t s = 0;
    for (int i = 0; i < k; ++i)
        s = std::min<int64_t>(s + (m + a[i] - 1) / a[i], 1e18);
    return s;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> n >> k;
    for (int i = 0; i < k; ++i)
        std::cin >> a[i];
    
    int64_t l = 0, r = 2e18;
    while (l < r) {
        int64_t m = (l + r + 1) / 2;
        if (count(m) <= n) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    
    int res = n - count(l);
    for (int i = 0; i < k; ++i) {
        pos[i] = (l + a[i] - 1) / a[i] * a[i];
        if (pos[i] == l && res > 0) {
            --res;
            pos[i] += a[i];
        }
    }
    
    int64_t mn = 2e18, mx = 0;
    for (int i = 0; i < k; ++i) {
        mx = std::max(mx, pos[i]);
        mn = std::min(mn, pos[i] - a[i]);
    }
    
    for (int i = 0; i < k; ++i) {
        for (int64_t j = pos[i] - a[i]; j >= mn; j -= a[i])
            ++cnt[j - mn];
        ans[i] = -cnt[pos[i] - a[i] - mn];
    }
    
    for (int i = mx - mn - 2; i >= 0; --i)
        cnt[i] += cnt[i + 1];
    for (int i = 0; i < k; ++i) {
        ans[i] += cnt[pos[i] - a[i] - mn];
        std::cout << n - ans[i] << " \n"[i == k - 1];
    }
    
    return 0;
}