题解 P1610 【鸿山洞的灯】
引领天下
2017-07-21 17:48:12
啊哈水题！
其实呢，我觉得这题大可不必用 dp，一个简单贪心搞定！
思路：
读进 $n$ 和 $dist$。
然后读入 $p_i$，排序。
之后就是核心代码了。
首先，题目中说如果 $p_{i+1}-p_{i-1}\le dist$ 就可以把 $p_i$ 关掉，那么，第 $1$ 盏肯定不能关，最后一盏也不能关。
于是，就有了从 1 到 $n-2$ 的循环（我用的是 0 下标）。
每次向前，找到离 $i$ 最近的一盏开着的灯，看看能不能把 $p_i$ 关掉（因为是从左往右找，所以右边的灯都未处理，是开着的）。
如果可以把 $p_i$ 关掉，那就把它标记为 0，$ans\leftarrow ans+1$
一趟循环走下来，答案就出来了。
此时，数组里除了必须留着的灯，其他都关掉了（标记为 0）。
最后输出就好了。
代码：
```cpp
#include <bits/stdc++.h>//万能头
using namespace std;
int p[100001],n,dist,i,ans;
int main(void){
scanf ("%d%d",&n,&dist);
for (;i<n;i++)scanf ("%d",&p[i]);
sort(p,p+n);//排序
for (i=1;i<n-1;i++)
if (p[i-1]!=0&&p[i+1]-p[i-1]<=dist)p[i]=0,ans++;//如果i-1是开着的，就可以不用开循环找了
else{//不然向前找
int j=i-1;
while (p[j]==0)j--;
if (p[i+1]-p[j]<=dist)p[i]=0,ans++;
}
printf ("%d",ans);//输出
}
```