「BZOJ1828」[Usaco2010 Mar] balloc 农场分配

2014年5月28日3,9610

Description

Input

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

Output

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

Sample Input

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

Sample Output

题解

贪心，按照右端点排序以后冲突的舍弃

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,ans;
struct data{int l,r;}a[N];
struct seg{int l,r,mn,tag;}t[N*3];
inline bool cmp(data a,data b)
{return a.r<b.r;}
void pushdown(int k)
{
     int l=t[k].l,r=t[k].r,tag=t[k].tag;
     if(l==r||!tag)return;
     t[k].tag=0;
     t[k<<1].mn-=tag;t[k<<1|1].mn-=tag;
     t[k<<1].tag+=tag;t[k<<1|1].tag+=tag;
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;
    if(l==r){t[k].mn=read();return;}
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r); 
    t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
}
bool ask(int k,int x,int y)
{
     pushdown(k);
     int l=t[k].l,r=t[k].r;
     if(l==x&&y==r)return t[k].mn>=1;
     int mid=(l+r)>>1;
     if(mid>=y)return ask(k<<1,x,y);
     else if(mid<x)return ask(k<<1|1,x,y);
     else return (ask(k<<1,x,mid)&ask(k<<1|1,mid+1,y));
     t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
}
void update(int k,int x,int y)
{
     pushdown(k);
     int l=t[k].l,r=t[k].r;
     if(l==x&&y==r){t[k].tag++;t[k].mn--;return;}
     int mid=(l+r)>>1;
     if(mid>=y)update(k<<1,x,y);
     else if(mid<x)update(k<<1|1,x,y);
     else {update(k<<1,x,mid);update(k<<1|1,mid+1,y);}
     t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
}
int main()
{
    n=read();m=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
        a[i].l=read(),a[i].r=read();
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
        if(ask(1,a[i].l,a[i].r))
        {
            update(1,a[i].l,a[i].r);
            ans++;
        }
    printf("%d",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 100005

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,m,ans;

struct data{int l,r;}a[N];

struct seg{int l,r,mn,tag;}t[N*3];

inline bool cmp(data a,data b)

{return a.r<b.r;}

void pushdown(int k)

{

int l=t[k].l,r=t[k].r,tag=t[k].tag;

if(l==r||!tag)return;

t[k].tag=0;

t[k<<1].mn-=tag;t[k<<1|1].mn-=tag;

t[k<<1].tag+=tag;t[k<<1|1].tag+=tag;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;

if(l==r){t[k].mn=read();return;}

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);

}

bool ask(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)return t[k].mn>=1;

int mid=(l+r)>>1;

if(mid>=y)return ask(k<<1,x,y);

else if(mid<x)return ask(k<<1|1,x,y);

else return (ask(k<<1,x,mid)&ask(k<<1|1,mid+1,y));

t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);

}

void update(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r){t[k].tag++;t[k].mn--;return;}

int mid=(l+r)>>1;

if(mid>=y)update(k<<1,x,y);

else if(mid<x)update(k<<1|1,x,y);

else {update(k<<1,x,mid);update(k<<1|1,mid+1,y);}

t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);

}

int main()

{

n=read();m=read();

build(1,1,n);

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

a[i].l=read(),a[i].r=read();

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

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

if(ask(1,a[i].l,a[i].r))

{

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

ans++;

}

printf("%d",ans);

return 0;

}

« 「BZOJ1634」[Usaco2007 Jan] Protecting the Flowers 护花「BZOJ1707」[Usaco2007 Nov] tanning分配防晒霜 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1828」[Usaco2010 Mar] balloc 农场分配

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论