BZOJ1828[USACO 2010 Mar Gold 2.Barn Allocation]——贪心+线段树

题目描述

输入

第1行：两个用空格隔开的整数：N和M * 第2行到N+1行：第i+1行表示一个整数C_i * 第N+2到N+M+1行： 第i+N+1行表示2个整数 A_i和B_i

输出

* 第一行： 一个整数表示最多能够被满足的要求数

样例输入

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

样例输出

3

对于区间覆盖这一类的问题，贪心是一个很好的思路。优先选右端点小的，这个很好证明：选了一段区间后，如果有更优解，也就是这段区间能被其他两段区间代替，那么这两个区间不会有相同部分，但因为这段区间之后的所有区间右端点都大于等于这个区间的右端点，所以假设中的更优解的那两段区间在这段区间上一定有重叠部分，所以假设不成立，没有更优解。所以将所有区间排个序然后依次选，用线段树维护一下区间最小值，如果所要加区间最小值<=0那么就加不了，否则就将区间每个数值都减1。

最后附上代码。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int l,r;
}s[100010];
int n,m,ans;
int a[100010];
int mi[400010];
int sign[400010];
void updata(int x)
{
    mi[x]=min(mi[x<<1],mi[(x<<1)+1]);
}
void pushdown(int x,int l,int r)
{
    if(sign[x])
    {
        mi[x<<1]+=sign[x];
        sign[x<<1]+=sign[x];
        mi[(x<<1)+1]+=sign[x];
        sign[(x<<1)+1]+=sign[x];
        sign[x]=0;
    }
}
void build(int x,int l,int r)
{
    int mid=(l+r)>>1;
    if(l==r)
    {
        mi[x]=a[l];
        return ;
    }
    build(x<<1,l,mid);
    build((x<<1)+1,mid+1,r);
    updata(x);
}
void change(int x,int l,int r,int L,int R,int v)
{
    int mid=(l+r)>>1;
    if(L<=l&&R>=r)
    {
        mi[x]+=v;
        sign[x]+=v;
        return ;
    }
    pushdown(x,l,r);
    if(L<=mid)
    {
        change(x<<1,l,mid,L,R,v);
    }
    if(R>=mid+1)
    {
        change((x<<1)+1,mid+1,r,L,R,v);
    }
    updata(x);
}
bool cmp(node x,node y)
{
    if(x.r!=y.r)
    {
        return x.r<y.r;
    }
    return x.l>y.l;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&s[i].l,&s[i].r);
    }
    sort(s+1,s+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        change(1,1,n,s[i].l,s[i].r,-1);
        if(mi[1]<0)
        {
            change(1,1,n,s[i].l,s[i].r,1);
        }
        else
        {
            ans++;
        }
    }
    printf("%d",ans);
}