加载中...

POJ 1716 - Integer Intervals


0x00 问题描述

给出数轴上的 n 个区间,每个区间都是连续的 int 区间。

现在要在数轴上任意取一堆元素,构成一个元素集合 V,要求每个区间和元素集合V的交集至少有两个不同的元素。

求集合 V 最小的元素个数。

0x10 解题思路

本题有两种解法: 贪心算法 或 差分约束

0x01 贪心算法

  1. 先对所有区间按末端点排序
  2. 取第 i 个区间的最后两个元素 Selem 和 Eelem
  3. 若第 i+1 个区间包含了这两个元素,则跳到下一个区间所取的 元素个数 +0
  4. 若第 i+1 个区间只包含了这两个元素中的一个(由于有序,所以必定是包含Eelem),则取第 i+1 个区间的最后一个元素,所取的 元素个数 +1。为了方便下一区间的比较,更新 Selem 和 Eelem 的值,使他们为当前 V 集合中最后的两个元素。
  5. 若第 i+1 个区间没有包含这两个元素,则第 i+1 个区间的最后两个元素,所取的 元素个数 +2。为了方便下一区间的比较,更新 Selem 和 Eelem 的值,使他们为当前V集合中最后的两个元素。
  6. Selem 初始化为第一个区间的最后倒数第 2 个元素7. Eelem 初始化为第一个区间的最后的元素
  7. 所取的元素个数初始化为 2 (就是 Selem 和 Eelem)

0x12 差分约束 + Relax

s[x] = 从0到x 的所有在集合中的数的个数,则 ai 到 bi 的个数即 S[bi] - S[ai-1]

因此有:

  • (1) S[bi] - S[ai-1] >= 2

又根据 s[x] 本身的性质,后面的一定不比前面的小,后面的最多比前面多一,有:

  • (2) s[i + 1] - s[i] >= 0
  • (3) s[i + 1] - s[i] <= 1

故建图,使图中每一组边,均满足(注意三条式子的不等号方向要一致,这个很重要):

  • S[ai - 1] <= S[bi] - 2
  • S[i] <= S[i - 1] + 1
  • S[i - 1] <= S[i]

上面三式,可把 s[x] 看作源点(假设存在)到各点的最短距离,初始化为 0;常数为边 (ai – 1,bi) 的边权。

当存在不满足这三条式子的边时,对这条边进行 Relax 操作,更新不等号左边的变量

其实就是 Bellman-Ford 算法的核心部分

  • if( S[ai - 1] > S[bi] – 2 ) S[ai - 1] = S[bi] – 2;
  • if( S[i] > S[i - 1] + 1 ) S[i] > S[i - 1] + 1;
  • if( S[i - 1] > S[i] ) S[i - 1] = S[i];

最后源点到最大顶点的距离减去源点到最小顶点的距离就是所求(其实一个单位距离就代表 V 中的一个元素;最小顶点到最大顶点其实就是所有输入的区间中,最小的左端点到最大的右端点这个范围)。

注意,经过我测试,本题变量的定义均要从全局定义,否则 WA,什么原因我也不清楚(变量和数组的大小都只有 10000,真是神了),只能说 POJ 太虐人了,白白耗了我一堆时间。

0x20 AC 源码

0x21 解题方法一: 贪心算法

//Memory Time 
//284K   94MS

/*Greed*/

#include<iostream>
#include<algorithm>
using namespace std;

typedef class
{
public:
    int s,e;
}interval;      //间隔(区间)

int cmp(const void* a,const void* b)
{
    interval* x=(interval*)a;
    interval* y=(interval*)b;
    return (x->e) - (y->e);  //对区间按末端点排序
}

int main(void)
{
    int n; //区间数
    while(cin>>n)
    {
        interval* inter=new interval[n];

        for(int i=0;i<n;i++)
            cin>>inter[i].s>>inter[i].e;

        qsort(inter,n,sizeof(interval),cmp);  //对区间按末端点排序

        int Selem=inter[0].e-1 , Eelem=inter[0].e;  //当前区间所取的两个元素,初始化为第0个区间最后两个元素
        int sum=2;  //至少取sum个元素才能保证每个区间至少含有其中的2个元素
        for(int k=1;k<n;k++)
            if(inter[k].s<=Selem)  //前一个区间所取的两个元素都在当前区间内
                continue;  //则当前区间无需取任何元素
            else if(inter[k].s<=Eelem)  //前一个区间所取的只有一个元素在当前区间内
            {
                Selem=Eelem;
                Eelem=inter[k].e;  //按序更新当前区间所取的两个元素:Selem与Eelem
                sum++;  //Eelem是新取的一个元素
            }
            else  //前一个区间所取的没有一个元素在当前区间内
            {
                Selem=inter[k].e-1;
                Eelem=inter[k].e;  //按序更新当前区间所取的两个元素:Selem与Eelem
                sum+=2;  //Selem与Eelem是新取的两个元素
            }
        cout<<sum<<endl;

        delete inter;
    }
    return 0;
}

0x22 解题方法二: 差分约束 + Relax

//Memory Time 
//296K  282MS 

/*Difference Constraints*/

#include<iostream>
using namespace std;

const int inf=20000;

class
{
    public:
        int s,e;
}inter[10001];

int dist[10001];  //源点到各点的距离
int n; //区间数
int upli;
int doli; // UpLimit , Downlimit 上下限

int main(int i)
{    
    while(cin>>n)
    {
        upli=0;
        doli=inf;

        /*Input*/

        for(i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            inter[i].s=a;
            inter[i].e=b+1;

            if(doli>inter[i].s)  //寻找最小的顶点
                doli=inter[i].s;
            if(upli<inter[i].e)  //寻找最大的顶点,inter[k].e必大于inter[k].s,因此无需再与inter[k].s比较
                upli=inter[i].e;

            dist[i]=0; //初始化源点到各点的距离
        }

        /*Bellman-Ford:Relax*/

        bool flag=true;
        while(flag)  //只要某一次Relax没有更新,说明最短路径已经查找完毕,或者部分点不可达,可以跳出relax
        {
            flag=false;
            for(i=0;i<n;i++)
                if(dist[ inter[i].s ]>dist[ inter[i].e ]-2)
                {
                    dist[ inter[i].s ]=dist[ inter[i].e ]-2;
                    flag=true;  //Relax对路径有更新
                }

            for(i=doli;i<upli;i++)
                if(dist[i+1]>dist[i]+1)
                {
                    dist[i+1]=dist[i]+1;
                    flag=true;
                }

            for(i=upli-1;i>=doli;i--)   //这里逆向松弛(从upli到doli)比正向松弛(从doli到upli)快了500ms
                if(dist[i] > dist[i+1])
                {
                    dist[i] = dist[i+1];
                    flag = true;
                }
        }
        cout<<dist[upli]-dist[doli]<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录