题解 P1610 【鸿山洞的灯】

Ophelia · 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;
}