洛谷P1937/USACO10MAR 仓配置Barn Allocation

@Pelom  October 28, 2019

题意

有$n$个点,$m$条线段,每个点最多被覆盖$c_i$次,求最多选择几条线段

数据范围:$1 \le n,m,c_i \le 100000$

题解

先按右端点为第一关键字升序,左端点为第二关键字降序排序
随后按顺序选择区间,能选则选
正确性证明:

  • 在右端点相同时,显然左端点越大区间长度越短,结果越优
  • 在右端点不同时,对于先选择的区间$i$与和$i$发生冲突的区间$j$,需要讨论的情况为$$l_i < l_j < r_i < r_j$$
    此时$[l_j,r_i]$的最小值为$0$(否则不会产生冲突)
    若用$j$替换掉$i$,会导致$[l_i,l_j]+1$(但无法利用,因为中间最小值为$0$),$[r_i,r_j]-1$,但答案不变,腾出来的空间没有用,相当于浪费掉了,因此不选更优

可否选择用线段树维护查询即可

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int INF=0x3f3f3f3f;
const int N=100000+10;
int n,m;
int c[N];
int ans;
struct D{
    int l,r;
    inline bool operator < (const D& x) const{
        return r==x.r?l>x.l:r<x.r;
    }
} d[N];
struct node{
    int w,tag;
} T[N<<2];
inline void pushUp(int rt){
    T[rt].w=min(T[ls].w,T[rs].w);
}
inline void pushDown(int rt){
    T[ls].w+=T[rt].tag;
    T[rs].w+=T[rt].tag;
    T[ls].tag+=T[rt].tag;
    T[rs].tag+=T[rt].tag;
    T[rt].tag=0;
}
void build(int rt,int l,int r){
    if(l==r){
        T[rt].w=c[l];
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushUp(rt);
}
void update(int rt,int l,int r,int L,int R,int k){
    if(l>=L && r<=R){
        T[rt].w+=k;
        T[rt].tag+=k;
        return ;
    }
    if(T[rt].tag)
        pushDown(rt);
    int mid=l+r>>1;
    if(L<=mid)
        update(ls,l,mid,L,R,k);
    if(R>mid)
        update(rs,mid+1,r,L,R,k);
    pushUp(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R){
        return T[rt].w;
    }
    if(T[rt].tag)
        pushDown(rt);
    int res=INF;
    int mid=l+r>>1;
    if(L<=mid)
        res=min(res,query(ls,l,mid,L,R));
    if(R>mid)
        res=min(res,query(rs,mid+1,r,L,R));
    pushUp(rt);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&d[i].l,&d[i].r);
    sort(d+1,d+m+1);
    for(int i=1;i<=m;i++){
        int t=query(1,1,n,d[i].l,d[i].r);
        if(t<=0)
            continue;
        ans++;
        update(1,1,n,d[i].l,d[i].r,-1);
    }
    printf("%d",ans);
    return 0;
}

添加新评论