已知n盏灯以及每盏灯的位置p[i]，p[i]均不相等，两盏相邻的灯当小于dist时，若这个安全距离里面还有灯是亮着时，就可以关掉该盏灯，(即若第i-1盏与第i+1盏的距离<=dist，则可以关掉第i盏)求在保证洞里的光线是充足的情况下，一段区域里能删除的灯的最大值。
距离洞口最近和最远的两盏灯必须是亮着
第一行两个数，n和dist
第二行n个数，即每盏灯的位置
一个数，即一段区域里能删除的灯的最大值。
3 3 1 2 3
1
n<=100000
贪心
#include<bits/stdc++.h> #include<math.h> using namespace std; int main() { int n,d,a[100000],b[100000],c=1,t=0; cin>>n>>d; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a,a+n); b[1]=a[1]; for(int i=2;i<=n-1;i++) { if(a[i]-b[c]<=d&&a[i+1]-b[c]<=d) {t++; continue; } else b[++c]=a[i]; } cout<<t; }
原文：https://www.cnblogs.com/lau1997/p/12534819.html