CF1839A The Good Array 题解

Furthe77oad · 2023-06-07 21:49:56 · 个人记录

CF1839A

写在最前

建议评红。

本题利用贪心思想，分类讨论后即可分析出正解。

分析

我们仔细地看完题。

首先考虑特殊情况 k=1 时，此时序列应该为连续的 1，所以答案为 n。其实就是，此时的序列，如要满足题目的要求，必然是 111... 这样连续的 1 组成的。

重要的是，想要序列 a 满足前 i 个元素中至少有 \lceil\frac{i}{k}\rceil 个元素为 1，我们可以很自然的想到贪心，根据贪心原理，我们只需要在 (1, k+1, 2k+1, \dots,xk+1,n) 的位置插入 1 即可。正确性很好证明，建议手摸一下自己研究。

在理解上述的分析后，请读者讨论接下来的问题：如果要满足另一要求，我们只需要额外插入的 1 的个数，进行分类讨论。见下。

设 x \times k + 1 与 n 之间的差值是 d，则 d=n \% k - 1

• 若 d \gt 0，则易得 0 \lt d \lt k，此时无需再多插 1，答案即为 \lfloor\frac{n-2}{k}\rfloor+2。

• 若 d = 0，则说明 x \times k + 1 与 n 重合，并且 n 又是满足第二要求的第一个 1 的位置，故此时无需多插 1，易得答案为\lfloor\frac{n-2}{k}\rfloor+2。

• 若 d = -1，则说明 xk+1=n+1，此时把 (x-1) \times k+1 作为新的 x' \times k+1，则答案仍为 \lfloor\frac{n-2}{k}\rfloor+2。

易证：时间复杂度为 \mathcal O(t)。

参考之码

#include <bits/stdc++.h>
using namespace std;
int t, n, k;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> k;
        cout << (n - 2) / k + 2 << "\n";
    }
    return 0;
}

写在最后

顺带一提，我在做的时候，没有完美地证明该题的正解，而是直接猜到了结论，所以由此观之，我们在网赛时，应该有意识的去培养我们的做题手感。

以上为个人观点。