7-5 sdut -C语言实验-节约用电
分数 13
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
山东理工大学计算机学院的9号楼里面有一条超长的走廊，可以看成是一条直线，走廊里一共有n盏电灯，每盏电灯的位置为ai。为了响应国家号召节约用电，学院决定关掉几盏灯，仅维持走廊的基本光照。
具体规则是：如果某盏灯的左右两盏亮着的灯距离不超过m米，就可以把这盏灯关闭，其中头尾两盏灯不允许关闭。
现在请你计算最多关掉多少盏灯。
题目来源：teacher Liu.
输入格式:
第一行两个整数n,m(2<=n<=100000,1<=m<=1000000)，分别表示电灯的盏数和最大距离m。
第二行n个整数，表示每盏灯的位置ai（1<=ai<=1000000）。
输出格式:
一个整数，表示最多关掉电灯的数量。
输入样例:
1. 4 5 2. 3 6 10 1
输出样例:
1
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include<stdio.h> int main() { int n,m; int i,j,t; scanf("%d %d",&n,&m); int *a=(int *)malloc(n*sizeof(int)); for(i=0; i<n;i++) { scanf("%d",&a[i]); } for(i=0;i<n-1;i++) { for(j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } int last=a[0]; int ans=0; for(i=1;i<n-1;i++) { if(a[i+1]-last<=m) { ans++; } else { last=a[i]; } } printf("%d\n",ans); return 0; }
