admin 管理员组

文章数量: 887021

程序设计

题目描述

学校里有一条超长的走廊，可以看成是一条直线。走廊里一共有n 盏电灯，每盏电灯的位置为 a_i。为了响应国家的号召节约用电，校长决定关掉几盏电灯，仅维持走廊的基本光照。具体规则是，如果某盏灯的左右两盏亮着的灯距离不超过m，就可以把这盏灯关闭。其中头尾两盏灯不允许关闭。

现在请你计算最多能关掉多少盏灯。

输入格式

第一行两个整数 n,m(2≤n≤105,1≤m≤106)，分别表示电灯的盏数和最大距离 mm。

第二行 n 个整数，表示每盏灯的位置ai​ (1≤ai​≤106)。

输出格式

一个整数，表示最多关掉电灯的数量。

输入样例

4 5
3 6 10 1

输出样例

1

#include <iostream>
#include <algorithm>
using namespace std;
int light[1000001];
int main(){int n,m,sum=0,l=1,g=3;cin>>n>>m;for(int i=1;i<=n;i++){cin>>light[i];}sort(light+1,light+n+1);while(g<=n){if(light[g]-light[l]<=m){g++;sum++;}else{l=g-1;g++;}}cout<<sum;return 0;
}

本文标签： 程序设计

版权声明：本文标题：程序设计 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/free/1697035743h260829.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。