D2cm6. 停车位

时间限制：1.0s 内存限制：256.0MB

问题描述

　　小蓝要在路边划分停车位。

　　他将路边可停车的区域划分为 L 个整数小块，编号 1 至 L。一个车位需要连续的 k 个小块，停车位不能重叠。有的小块属于井盖、消防通道等区域，不能停车。

　　请问小蓝最多划分出多少个停车位？

输入格式

　　输入的第一行包含三个整数 L、k、n，分别表示小块数量、一个车位需要的小块数量和不能停车的小块数量，相邻整数之间用一个空格分隔。

　　第二行包含 n 个整数 a[1], a[2], ..., a[n]，按从小到大的顺序排列，相邻的整数间用空格分隔，表示这些位置不能停车。

输出格式

　　输出一行包含一个整数，表示答案。

样例输入

100 10 2

25 91

样例输出

8

评测用例规模与约定

　　对于 50% 的评测用例，2 <= L <= 1000，1 <= k <= 10，1 <= n <= 100。

　　对于所有评测用例，2 <= L <= 100000000，1 <= k <= 1000，1 <= n <= 100000。

90分AC，10分TLE

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int L, k, n;
	cin >> L >> k >> n;
	vector<bool> can_park(L + 1, true);
	for (int i = 0; i < n; i++) {
		int pos;
		cin >> pos;
		can_park[pos] = false;
	}
	int count = 0;
	for (int i = 1; i <= L - k + 1; i++) {
		bool canPark = true;
		for (int j = i; j < i + k; j++) {
			if (!can_park[j]) {
				canPark = false;
				break;
			}
		}
		if (canPark) {
			count++;
			i += k - 1;
		}
	}
	cout << count << endl;
	return 0;
}