题解 P4519 【[COCI2017-2018 Contest4]Rasvjeta 】
要想开始着手切这道题，那必须得知道题面讲什么，很不幸，这道题没有翻译……
那么我来翻译一下吧！
题目描述：
现在是夜幕降临的时候。在N米长的街道上有M个路灯（街道的米数用1
到N之间的数字表示）。每一盏灯都会点亮它所在街道的相应米数，并
在该位置的左右两侧各亮K米。换句话说，如果灯光位于X米处，它将
照亮从X-K到X+K的所有米的街道，包括X-K。当然，一米的街道有可能
被多个路灯照亮。所有的灯都有不同的位置。
问题是，有一种可能性是，路灯并没有照亮整条街道的N米。您的任务
是确定需要安装的最小数量的额外灯光（位置从1到N），以便照亮整
条街道。
输入格式：
输入的第一行包含街道的米数N（1≤N≤1000）。
第二行输入包含灯数M（1≤M≤N）。
第三行包含照亮左右米数的K（0≤K≤N）。
下面的M行中的每一行都包含一个数字。这些数字按升序排序，代表
每个路灯的位置。
该位置将在区间[1，N]之间。输出格式：
必须按照题目要求输出。现在让我们分析这道题。
第一眼看上去是个模拟。
我们只要打个数组存储每一米街道的状态即可，因为题面说一米的街道可能被多个路灯同时照亮，所以不用考虑亮度问题，照到的打标记
我们已经解决了第一个问题。
那么接下来就是整个题目的精髓：贪心。
怎么贪呢？
尽量少放灯，换而言之就是让最少的灯发挥最大的价值，即在你放置的灯中，尽可能地让两盏灯之间没有互交的地方。
来看看我的办法：每当我们找到一个没有被照到的阴暗处时，放灯。但是注意，不论是几米的阴暗部分，至少要放一盏灯，然后在你当前的位置上向前
然后莫忘了结尾特判。
还有一件事，超出区间会RE，最好小心点哦。
AC Code
#include<iostream>
#include<cmath>
using namespace std;
int a[10000001];
int main()
{
int n,m,k,kk;
int ans=0;
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
cin>>kk;
for(int j=max(kk-k,1);j<=min(kk+k,n);j++)//照到的部分打标记，还有在区间内办事
{
a[j]=1;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]!=1)
{
for(int j=i;j<=min(i+2*k,n);j++)//每找到一个向后打2K个标记，还有在区间内办事
a[j]=1;
ans++;
}
}
if(a[n]==0)ans++;//结尾特判
cout<<ans;
return 0;
}