Codeforces Round 876 (Div. 2)题解

Codeforces Round 876 (Div. 2)

A. The Good Array

标签

greedy math

题意

对于任意 \(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<d<k\)，此时无需再多插 \(1\)，答案为 \(\lfloor\frac{n-1}{k}\rfloor+2\)；若 \(d=0\)，则说明 \(xk+1\) 与 \(n\) 重合，而 \(n\) 又为满足第二要求的第一个 \(1\) 的位置，故此时无需多插 \(1\)，进而答案为 \(\lfloor\frac{n-1}{k}\rfloor+1\)；若 \(d=-1\)，则说明 \(xk+1=n+1\)，此时把 \((x-1)k+1\) 作为新的 \(x'k+1\)，答案仍为 \(\lfloor\frac{n-1}{k}\rfloor+2\)。
   4， 时间复杂度为 \(\mathcal O(t)\)。

代码

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
using 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\) 的判断条件。