LUOGU P1937 [USACO10MAR]仓配置Barn Allocation

解题思路

扫了一眼觉得是贪心+线段树，结果贪心的时候刚开始按区间长度排的序。。这还有82分，后来叉了自己，换成按右端点排序过了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN = 100005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return f?x:-x;

}

struct Data{

    int l,r;

}data[MAXN];

int n,m,ans;

int lazy[MAXN<<2],Min[MAXN<<2];

inline void pushdown(int x){

    lazy[x<<1]+=lazy[x];lazy[x<<1|1]+=lazy[x];

    Min[x<<1]-=lazy[x];Min[x<<1|1]-=lazy[x];

    lazy[x]=0;

}

void build(int x,int l,int r){

    if(l==r){

        Min[x]=rd();

        return;

    }

    int mid=l+r>>1;

    build(x<<1,l,mid);build(x<<1|1,mid+1,r);

    Min[x]=min(Min[x<<1],Min[x<<1|1]);

}

int query(int x,int l,int r,int L,int R){

    if(L<=l && r<=R) return Min[x];

    int mid=l+r>>1,ret=0x3f3f3f3f;

    if(lazy[x]) pushdown(x);

    if(mid>=L) ret=min(ret,query(x<<1,l,mid,L,R));

    if(mid<R)  ret=min(ret,query(x<<1|1,mid+1,r,L,R));

    return ret;

}

void update(int x,int l,int r,int L,int R,int k){

    if(L<=l && r<=R) {

        Min[x]-=k;

        lazy[x]+=k;

        return;

    }

    int mid=l+r>>1;

    if(lazy[x]) pushdown(x);

    if(mid>=L) update(x<<1,l,mid,L,R,k);

    if(mid<R)  update(x<<1|1,mid+1,r,L,R,k);

    Min[x]=min(Min[x<<1],Min[x<<1|1]);

} 

inline bool cmp(Data A,Data B){

    if(A.r==B.r)

        return A.l>B.l;

    return A.r<B.r;

}

int main(){

    n=rd();m=rd();build(1,1,n);

    for(register int i=1;i<=m;i++) data[i].l=rd(),data[i].r=rd();

    sort(data+1,data+1+m,cmp);

    for(register int i=1;i<=m;i++)

        if(query(1,1,n,data[i].l,data[i].r)>0) {

            ans++;

            update(1,1,n,data[i].l,data[i].r,1);

        }

    cout<<ans<<endl;

    return 0;

}

巴特西

LUOGU P1937 [USACO10MAR]仓配置Barn Allocation

解题思路

代码

最新文章

热门文章