题解 P1610 【鸿山洞的灯】

发表于 更新于 阅读次数： Waline：
P1610 【鸿山洞的灯】题解。

啊哈水题！

其实呢，我觉得这题大可不必用dp，一个简单贪心搞定！（没准我用的是dp，自己因为是贪心）

咳咳，思路吗……读进n和dist，这个不用讲吧

然后读入pi，排序（别信样例，没准是乱序，反正快排一下也用不了多少时间）

之后就是核心代码了

首先，题目中说如果 p[i+1]-p[i-1]<=dist 就可以把pi关掉，那么，第1盏肯定不能关，最后一盏也不能关（具体自行理解）

于是，就有了从1到n-2的循环（我用的是0下标）

每次向前，找到离i最近的一盏开着的灯，看看能不能把pi关掉（因为是从左往右找，所以右边的灯都未处理，是开着的）

如果可以把pi关掉，那就把它标记为0，ans++

一趟循环走下来，答案就出来了

此时，数组里除了必须留着的灯，其他都关掉了（标记为0）

最后输出就好了

奉上0msAC的代码（c++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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);//输出
}