欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2376 浅谈一类区间覆盖问题的贪心解法

程序员文章站 2024-01-05 20:56:52
...

POJ 2376 浅谈一类区间覆盖问题的贪心解法
世界真的很大
曾经有过那么一段时间,我是研究过这个问题的
今天在做一道其他题的时候,这个问题作为一个子问题出现了,然后,然后,然后我蒙了你知道吧?
基本上搞忘了,模模糊糊有一点有点印象
赶紧的做一道水题复习一下
立个flag我不会搞忘

看题先:

description

farmer John要安排他的牛清理牛棚,一共有T个牛棚要清理,每头牛可以清理相邻的牛棚。比如,一头牛可以清理4-7号牛棚。当然了,牛清理的牛棚可以重叠。现在要你求出可以完成牛棚的清理的最少头牛的个数,不可以就输出-1.

input

  • Line 1: Two space-separated integers: N and T
  • Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

output

  • Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.

这道题是裸的区间覆盖贪心
方法是,先把所有区间按照L排序,然后挨着挨着选,每次选左区间在已覆盖范围内,右区间尽量大的
为什么这样是对的,嗯。。。。。显然?
可以看一下这篇博客
主要是复习一下结论性的东西和“板子”

完整代码:

#include<stdio.h>
#include<algorithm>
using namespace std;

struct speech
{
    int lf,rg;
}sph[100010];

int n,m,ans=0;

bool cmp(const speech &a,const speech &b)
{
    if(a.lf==b.lf) return a.rg>b.rg;
    return a.lf<b.lf;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&sph[i].lf,&sph[i].rg);
    sort(sph+1,sph+n+1,cmp);
    int k=0,rg=0;
    while(rg<m)
    {
        int now=rg,cnt=0;
        while(k<=n && sph[k].lf<=rg+1)
            now=max(now,sph[k].rg),k++,cnt++;
        if(!cnt) break ;
        rg=now,ans++;
    }
    if(rg==m) printf("%d\n",ans);
    else printf("-1\n");
    return 0;
} 
/*
EL PSY CONGROO
*/

嗯,就是这样

相关标签: poj

上一篇:

下一篇: