自动搬运

查看原文

来自洛谷，原作者为

	Ophelia **

搬运于2025-08-24 21:27:03，当前版本为作者最后更新于2019-01-05 21:02:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解做法贪心。

虽然其他题解里已经有了贪心的做法，但是这个做法加了一个小优化，使得代码更加快速(时间复杂度$O(NlogN)$)，而且更简洁。

排序是必要的。然后每次按顺序从前向后找是否符合条件，符合条件就关掉。

另外，第一盏和最后一盏等必须亮着，所以不找。

#include<bits/stdc++.h>
using namespace std;
int n,dist,a[100002],sum;
int main()
{
	cin>>n>>dist;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=2; i<=n-1; i++)
	{
		if(a[i+1]-a[i-1]<=dist)
		{
			a[i]=a[i-1];\\优化的核心部分。我们使用递推优化。其本质是关灯时把前一盏灯移到当前这一盏灯的位置上，防止下次计算时寻找前一盏灯。有类似链表删除的作用。
			sum++;
		}
	}
	cout<<sum<<endl;
	return 0;
}

2019.1.9 更新

递推优化的实质是采用了一种链表的想法，只不过使用了递推的方式来代替。这次我们使用链表（数组模拟链表）来进行前一盏灯与后一盏灯的判断，不过本质依然是贪心。

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define inf 99999999
using namespace std;
typedef double db;
typedef long long ll;
int n,dist,sum;
struct NODE
{
	int data,pre,nxt;
}node[10001];//建立双向链表
int cmp(const NODE &a,const NODE &b)
{
	return a.data<b.data;
}//传入sort的排序规则函数，按照数据的大小排序
void del(int x)//删除下标为x的节点
{
	node[node[x].pre].nxt=node[x].nxt;//前一个节点的后一个节点改为当前节点的后一个节点
	node[node[x].nxt].pre=node[x].pre;//后一个节点的前一个节点改为当前节点的前一个节点
}
int main()
{
	cin>>n>>dist;
	node[1].pre=node[1].nxt=0;//初始化
	for(int i=1;i<=n;i++)
		cin>>node[i].data;//输入数据
	sort(node+1,node+1+n,cmp);//排序贪心
	for(int i=2;i<=n-1;i++)
	{
		node[i].pre=i-1;
		node[i].nxt=i+1;//建立前一盏和后一盏的联系。
	}
	for(int i=2;i<=n-1;i++)//第一个和最后一个不要操作
	{
		if(node[node[i].nxt].data-node[node[i].pre].data<=dist)//下一个节点的数据（下一盏灯的位置）减上一个节点的数据（上一盏灯的位置）<=dist的话
		{
			del(i);//删除当前节点
			sum++;//计数器++
		}
	}
	cout<<sum<<endl;
	return 0;
}