P2207 Photo

佚名 5年前 (2019-05-13) 随笔 1401人围观抢沙发百度已收录

　　贪心区间选点问题。　　

　　对于两个牛不能出现在同一个photo中，可以看作对于这一段区间，必须要一个断点给这个区间的端点分开。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　那么对于若干条这样的线段，问题就转化成了：最少需要多少断点，可以将所有线段都分开，即每个区间线段上都有一个断点。

　　这就可以贪心求解了，先排序再从左往右扫，定义last为当前处理的能用一个断点分割的线段集合中，断点能取的最靠右的位置。这样对于一条新的线段，我们只要比较这个线段能不能用last或者比last靠前的断点，不能的话就新开一个集合，能的话再看看加了这条线断之后，现在的last是多少。

　　对于边界是否取等号问题，最简单的方法是自己代一下。但实际上我们并不能用端点作为断点（怎么这么拗口），所以新线段左端点等于last也得新开一个集合。

　　代码 time 咯——

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 2000
struct node
{
    int L,R;
    friend bool operator < (node a,node b)
    {
        if(a.L==b.L) return a.R<b.R;
        return a.L<b.L;
    }
} q[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&q[i].L,&q[i].R);
        if(q[i].L>q[i].R) swap(q[i].L,q[i].R);
    }
    sort(q+1,q+k+1);
    int last=-1,ans=1;
    for(int i=1;i<=k;i++)
    {
        int L=q[i].L;
        if(L>=last)
        {
            ans++;
            last=q[i].R;
        }
        else if(q[i].R<last) last=q[i].R;
    }
    printf("%d\n",ans);
    return 0;
}