自动搬运

查看原文

来自洛谷，原作者为

	Kaedeuim 来了没有喜多郁代

搬运于2025-08-24 22:00:58，当前版本为作者最后更新于2020-07-25 00:18:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

要想开始着手切这道题，那必须得知道题面讲什么，很不幸，这道题没有翻译……

那么我来翻译一下吧！

题目描述：

现在是夜幕降临的时候。在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]之间。

输出格式：

必须按照题目要求输出。

$\text{---------不华丽的分割线---------}$

现在让我们分析这道题。

第一眼看上去是个模拟。

我们只要打个数组存储每一米街道的状态即可，因为题面说一米的街道可能被多个路灯同时照亮，所以不用考虑亮度问题，照到的打标记$1$，没照到的默认为$0$。

我们已经解决了第一个问题。

那么接下来就是整个题目的精髓：贪心。

怎么贪呢？

尽量少放灯，换而言之就是让最少的灯发挥最大的价值，即在你放置的灯中，尽可能地让两盏灯之间没有互交的地方。

来看看我的办法：每当我们找到一个没有被照到的阴暗处时，放灯。但是注意，不论是几米的阴暗部分，至少要放一盏灯，然后在你当前的位置上向前$2K$的距离打上标记，这才是贪心精髓。

然后莫忘了结尾特判。

还有一件事，超出区间会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; 
}

说句闲话：我要是修这条路的人，一定会被晚上开车经过这里的人喷死

管理员求过~