题意简述： 给定长度为 n 的数组 a_i。每次你可以花费 1 的代价使 a_i 加上或者减去 1。要求最小化代价使得所有 a_i 都是质数 k 的倍数。n \leq 10^5,\ a_i \leq 10^{12}。 思路分析： 首先我们令 k = 2，得到 ans \leq n。也就是说，对于最优解的画面，至多有 \lfloor \frac n 2 \rfloor 个整数的变化幅度超过 1。 设定阀值 \omega，我们随机从 a_{1 \dots n} 中选择 k 个数 x_{1 \dots k}，每次检查 x-1,x,x+1 的每个质因子是否为答案。复杂度为 O(n \sigma (a) Read more…
做本题之前建议先完成本题的简化版。 思路分析 这题 hard version 的主要思想与 easy version 相同。我们唯一应替换的是搜索的方式。用二分搜索替换线性搜索可以将时间复杂度从 O(n^2) 降低到 O(n \log n)。 很明显，我们可以在此处应用二分搜索，因为如果我们可以在 d 这天订购所有微交易，那么我们就可以在 d+1 天的所有订单中订购所有微交易（即使使用 d 天的答案，也可以在 d+1 的日子不做任何交易）。 代码： 本题： #include <bits/stdc++.h> using namespace std; int n, m; vector<int> k; vector<pair<int, int>> q(200001); bool can(int day) { vector<int> lst(n, -1); for (int i = 0; Read more…