(相关资料图)

Codeforces Round 876 (Div. 2)

A. The Good Array

标签

greedymath

题意

对于任意 \(i\in\{1,2,\dots,n\}\)，要求数列 \(a\) 满足前 \(i\) 个元素中至少有 \(\lceil\frac{i}{k}\rceil\) 个元素为 \(1\)，后 \(i\) 个元素中至少有 \(\lceil\frac{i}{k}\rceil\) 个元素为 \(1\)。

思路

1. 考虑特殊情况 \(k=1\)，因为此时序列 \(1\) 的插入点连续，所以答案为 \(n\)。
2. 欲令数列 \(a\) 满足前 \(i\) 个元素中至少有 \(\lceil\frac{i}{k}\rceil\) 个元素为 \(1\)，根据贪心只需要在 \(1, k+1, 2k+1, \dots,xk+1,n\) 的位置插入 \(1\)。在该前提下，讨论欲满足另一要求需要额外插入的 \(1\) 的个数，分类讨论。
3. 若 \(xk+1\) 与 \(n\) 之间的差值 \(d=n\%k-1> 0\)，则易得 \(0

代码

#include #define ll long long#define ld long double#define ull unsigned long longusing namespace std;int t, n, k; int main (){scanf ("%d", &t);while (t --) {scanf ("%d %d",&n, &k);if (k == 1) printf ("%d\n", n);else if (n % k - 1 != 0) printf ("%d\n", (n - 1) / k + 2);else printf ("%d\n", (n - 1) / k + 1);}return 0;}

收获

1. 脑子混乱时，静下心来重新发现性质。比如，该题最关键的性质为除去位置 1 和位置 n 处的 \(1\)，其他位置的 \(1\) 之间的差值恒为 \(k\)，以及对是否需要额外插 \(1\) 的判断条件。

关键词：