334

B-Christmas Trees

Description

有一条向东西两侧无限延伸的道路，从这条道路上的某一参考点向东 $x$ 米处的点的坐标定义为 $x$ 。其中，从参考点向西 $x$ 米处的一点的坐标为 $- x$ 。

斯努克将从坐标为 $A$ 的点开始，以 $M$ 米的间隔在路上的各点摆放圣诞树。换句话说，他将在每一个可以用某个整数 $k$ 表示为 $A + k M$ 的点上摆放一棵圣诞树。

高桥和青木分别站在坐标为 $L$ 和 $R$ 的点上。 $(L \leq R)$ 。求在高桥和青木之间（包括他们所站的点）将会有多少棵圣诞树。

Constraints

$- 10^{18} \leq A \leq 10^{18}$
$1 \leq M \leq 10^{9}$
$- 10^{18} \leq L \leq R \leq 10^{18}$
All input values are integers.

Input

$\begin{aligned} A & M & L & R \end{aligned}$

Output

打印将在高桥和青木之间设置的圣诞树数量（包括他们所站的位置）。

Sample Input

5 3 -1 6

Sample Output

Solution

首先，让我们通过从 $L$ 和 $R$ 中减去 $A$ 来简化问题，这样圣诞树就站在坐标的倍数上。

设 $k$ 为站在坐标 $k M$ 处的树的索引。设 $l$ 为站在严格小于 $L$ 的坐标处的最东边的树的索引，

而 $r$ 则是站在坐标小于或等于 $R$ 的最东边的树的索引。那么答案就是 $r - l$ 。

现在剩下的是找到站在小于或等于 $x$ 的坐标处的最东边的树的索引，对于某个 $x$ ；这简单地表示为 $⌊ \frac{x}{M} ⌋$ 。请注意，当 $x$ 为负数时，根据编程语言的不同，找到 $⌊ \frac{x}{M} ⌋$ 的方法也有所不同。（例如，在 C++中，你不能简单地写 x/M。）此外，通过对浮点数进行求值以获得实数然后进行取下限可能会因为精度误差而导致错误的值，所以请小心。

Code

ans=(R - A - ((R - A) % M + M) % M) / M - (L - 1 - A - ((L - 1 - A) % M + M) % M) / M
官方题解是

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll floor(ll x, ll m) {
    ll r = (x % m + m) % m;
    return (x - r) / m;
}
int main() {
    ll a, m, l, r;
    cin >> a >> m >> l >> r;
    l -= a, r -= a;
    cout << floor(r, m) - floor(l - 1, m) << endl;
}

C-Socks 2

问题陈述

高桥有 $N$ 双袜子，其中 $i$ 双由两只颜色为 $i$ 的袜子组成。一天，高桥在整理抽屉时发现自己丢失了 $A_{1}, A_{2}, \dots, A_{K}$ 种颜色的袜子各一只，于是他决定用剩下的 $2 N - K$ 只袜子做 $⌊ \frac{2 N - K}{2} ⌋$ 双新袜子，每双由两只袜子组成。一双颜色为 $i$ 的袜子和一双颜色为 $j$ 的袜子的怪异度定义为 $| i - j |$ ，高桥希望将总怪异度最小化。

求用剩下的袜子做成 $⌊ \frac{2 N - K}{2} ⌋$ 对时，总奇异度的最小值。请注意，如果 $2 N - K$ 是奇数，那么将有一只袜子不包含在任何一对袜子中。

Constraints

$1 \leq K \leq N \leq 2 \times 10^{5}$
$1 \leq A_{1} < A_{2} < \dots < A_{K} \leq N$
All input values are integers.

Input

$\begin{aligned} N K \\ A_{1} A_{2} & \dots A_{K} \end{aligned}$

Output

将最小总怪异度打印为整数。

Sample Input

4 2
1 3

Sample Output

Notes

下面，让 $(i, j)$ 表示一对颜色为 $i$ 的袜子和一对颜色为 $j$ 的袜子。
颜色为 $1, 2, 3, 4$ 的袜子分别有 $1, 2, 1, 2$ 只。创建 $(1, 2), (2, 3), (4, 4)$ 这对袜子后，总奇异度为 $| 1 - 2 | + | 2 - 3 | + | 4 - 4 | = 2$ ，即最小奇异度。

Solution

首先，最优的方案是匹配他没有丢失的袜子。

证明

对于他没有使用过的颜色 $p$ ，考虑一个情况，其中两只颜色为 $p$ 的袜子没有配对。当它们和颜色为 $A_{i}$ 和 $A_{j}$ 的袜子一起时，根据三角不等式 $| A_{i} - A_{p} | + | A_{j} - A_{p} | \geq | A_{i} - A_{j} | = | A_{i} - A_{j} | + | A_{p} - A_{p} |$ ，所以通过将 $(A_{p}, A_{p})$ 和 $(A_{i}, A_{j})$ 配对，而不是 $(A_{p}, A_{i}), (A_{p}, A_{j})$ ，总的奇异度不会增加。当一个颜色为 $p$ 的袜子没有与任何袜子配对，而另一个袜子配对的颜色是另一个颜色 $A_{i}$ 时，总的奇异度不会增加，通过将 $(A_{p}, A_{p})$ 配对，而不是将 $(A_{p}, A_{i})$ 配对后留下 $A_{p}$ 未配对。因此，我们可以假设两只颜色为 $A_{p}$ 的袜子会在最优解中始终配对。

因此，这个问题可以被看作是一个问题，要求从颜色 $A_{1}, A_{2}, \dots, A_{K}$ 中的每一个颜色中挑选一只袜子，制造 $⌊ \frac{K}{2} ⌋$ 对袜子。

如果 $K$ 是偶数，最优的配对方式似乎是配对 $(A_{1}, A_{2}), (A_{3}, A_{4}), \dots, (A_{K - 1}, A_{K})$ ，这是确实的情况。

证明

我们通过归纳进行证明。只要证明在最优解中颜色 $A_{1}$ 总是与颜色 $A_{2}$ 配对。

我们通过反证法证明上面的结论。在一个最优解中，假设颜色 $A_{1}$ 与颜色 $A_{i} (i > 2)$ 配对，并且颜色 $A_{2}$ 与颜色 $A_{j}$ 配对。那么由于 $A_{1} < A_{2} < A_{i}, A_{j}$ ，我们有 $| A_{i} - A_{1} | + | A_{j} - A_{2} | > | A_{2} - A_{1} | + | A_{j} - A_{i} |$ ，所以将 $(A_{1}, A_{2})$ 和 $(A_{i}, A_{j})$ 配对，而不是配对 $(A_{1}, A_{i})$ 和 $(A_{2}, A_{j})$ 会减小总的奇异度，这违反了最优性。

当 $K$ 是奇数时，问题就出现了。在这种情况下，我们可以在剩下的袜子中暴力解决唯一没有配对的颜色的问题，最优的方法可以像我们处理偶数 $K$ 一样找到。当剩下的袜子配对时，最小的总奇异度可以在 $O (N)$ 的时间内找到，但这导致了 $O (N^{2})$ 的复杂度。而实际上，我们可以预先计算当前几只袜子配对时的总的奇异度，例如 $presum [2] = (A_{2} - A_{1}), presum [4] = (A_{4} - A_{3}) + (A_{2} - A_{1}), presum [6] = (A_{6} - A_{5}) + (A_{4} - A_{3}) + (A_{2} - A_{1}), \dots$ ，以类似前缀和的方式。同样，可以找到“后缀和”。因此，通过这种方法，问题可以在总共 $O (N)$ 的时间内解决。

额外信息：当 $K$ 是奇数时，相比于对每只未配对的袜子暴力尝试，我们可以只尝试 $A_{1}, A_{3}, A_{5}, \dots, A_{K}$ （证明省略）。在下面的示例代码中，我们采用了这种方法来简化实现。

Code

需要计算前缀(pre)和后缀(suf)

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(k);
    for (int &i: a) cin >> i;
    vector<int> pre(k + 1), suf(k + 1);
    for (int i = 1; i <= k; i++) {
        pre[i] = pre[i - 1];
        if (i % 2 == 0) pre[i] += a[i - 1] - a[i - 2];
    }
    for (int i = k - 1; i >= 0; i--) {
        suf[i] = suf[i + 1];
        if ((k - i) % 2 == 0) suf[i] += a[i + 1] - a[i];
    }
    int ans = 1e9;
    for (int i = 0; i <= k; i += 2) {
        ans = min(ans, pre[i] + suf[i]);
    }
    cout << ans << endl;
}