📝 题目大意

高桥君按 $N$ 次按钮，每次按按钮可获得 $1$ 颗糖果，但距离上次获得糖果的时间不足 $C$ 秒时无法获得。给定 $N$ 次按按钮的时刻 $T_1 < T_2 < \dots < T_N$，问最多能获得多少颗糖果。

💡 解题思路

1. 题目分析：$N \le 100$，$C \le 1000$，$T_i$ 严格递增且 $\le 1000$。数据范围极小，暴力即可。核心是理解"距离上次获得糖果的时间"而非"距离上次按按钮的时间"——即一旦某次按按钮没有获得糖果，下一次判断时仍然参考上一次真正获得糖果的时刻。

2. 算法推导：这是一个经典的贪心问题。设 $sc$ 为上一次获得糖果的时刻（初始为 $T_1$，因为第一次按按钮一定能获得糖果，答案 $ans$ 初始为 $1$）。遍历 $i = 2$ 到 $N$：

   • 若 $T_i - sc \ge C$，说明间隔足够，可以获得糖果：ans++，并更新 $sc = T_i$；
   • 否则，间隔不足，无法获得糖果，$sc$ 保持不变。

   贪心正确性：每次遇到能拿糖果的时刻立即拿，因为拿得越早，$sc$ 越小，后续能拿糖果的条件越宽松（$T_j - sc \ge C$ 更容易满足）。如果选择跳过当前能拿的时刻，$sc$ 不变（仍为更早的时刻），虽然对当前这步看起来"不亏"，但并不会增加总糖果数——因为跳过的这颗糖果永远失去了，而后续能拿的糖果即便跳过当前也能拿。因此"能拿就拿"是最优策略。

3. 边界与细节：

   • 第一次按按钮一定能获得糖果（没有"上次获得糖果"的限制），所以 $ans$ 初始化为 $1$，$sc$ 初始化为 $T_1$。
   • $T_i$ 可能为 $0$（时刻 $0$），不影响逻辑。
   • $N = 1$ 时循环不执行，直接输出 $1$，正确。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，仅需一次遍历。
• 空间复杂度：$O(N)$（存储数组），也可优化至 $O(1)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;

int main () {
	int n, c, a[1005], ans = 1, sc;
	scanf("%d%d", &n, &c);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sc = a[1];                        // 第一次按按钮一定能获得糖果
	for (int i = 2; i <= n; i++) {
		if (a[i] - sc >= c) {         // 距离上次获得糖果的时间 ≥ C，可以再拿
			ans++;
			sc = a[i];                // 更新上一次获得糖果的时刻
		}
		// 否则间隔不足，无法获得糖果，sc 保持不变
	}
	printf("%d", ans);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main () {
	int n,c,a[1005],ans = 1,sc;
	scanf("%d%d",&n,&c);
	for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
	sc = a[1];
	for (int i = 2;i <= n;i++) {
		if (a[i] - sc >= c) {
			ans++;
			sc = a[i];
		}
	}
	printf("%d",ans);
	return 0;
}