USACO[Elite 2010 March Competition/gold]balloc

恩,贪心+线段树维护。

CODE:

/*

PROG: balloc

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-27

DESCRIPTION:

TITLE: Barn Allocation [Jaehyun Park/Jeffrey Wang, 2010]

CONTENT:

Farmer John recently opened up a new barn and is now accepting stall

allocation requests from the cows since some of the stalls have a

better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered

1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow i

may request a contiguous interval of stalls (A_i, B_i) in which to

roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to

wander among all the stalls in the range A_i..B_i (and the stalls

must always have the capacity for her to wander).

Given M (1 <= M <= 100,000) stall requests, determine the maximum

number of them that can be satisfied without exceeding stall

capacities.

Consider both a barn with 5 stalls that have the capacities shown

and a set cow requests:

Stall id:    1   2   3   4   5

           +—+—+—+—+—+

Capacity:  | 1 | 3 | 2 | 1 | 3 | 

           +—+—+—+—+—+

Cow 1       XXXXXXXXXXX             (1, 3)

Cow 2           XXXXXXXXXXXXXXX     (2, 5)

Cow 3           XXXXXXX             (2, 3)

Cow 4                   XXXXXXX     (4, 5)

FJ can’t satisfy all four cows, since there are too many requests

for stalls 3 and 4.

Noting that Cow 2 requests an interval that includes stalls 3 and

4, we test the hypothesis that cows 1, 3, and 4 can have their

requested stalls. No capacity is exceeded, so the answer for this

set of data is 3 — three cows (1, 3, and 4) can have their requests

satisfied.

MEMORY LIMIT: 32 MB

TIME LIMIT: 2 seconds

PROBLEM NAME: balloc

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..N+M+1: Line i+N+1 contains two integers: A_i and B_i

SAMPLE INPUT (file balloc.in):

5 4

1

3

2

1

3

1 3

2 5

2 3

4 5

OUTPUT FORMAT:

* Line 1: The maximum number of requests that can be satisfied

SAMPLE OUTPUT (file balloc.out):

3

*/

#include <stdio.h>

 

#define MAXN 100000

#define MAXM 100000

#define oo ~(1<<31)

 

int N,M;

int C[MAXN+1];

int A[MAXM],B[MAXM];

int answer;

int st_min[MAXN<<2],st_cnt[MAXN<<2];

 

void quick_sort(int L,int R)

{

    int mid_A=A[(L+R)>>1];

    int mid_B=B[(L+R)>>1];

    int i=L,j=R;

    while (i<=j)

    {

        while (A[i]<mid_A||(A[i]==mid_A&&B[i]>mid_B)) i++;

        while (A[j]>mid_A||(A[j]==mid_A&&B[j]<mid_B)) j–;

        if (i<=j)

        {

            int swap;

            swap=A[i];

            A[i]=A[j];

            A[j]=swap;

            swap=B[i];

            B[i]=B[j];

            B[j]=swap;

            i++;

            j–;

        }

    }

    if (L<j) quick_sort(L,j);

    if (i<R) quick_sort(i,R);

}

int min(int a,int b)

{

    return a<b?a:b;

}

void build(int L,int R,int root=1)

{

     int LL=L,LR=(L+R)>>1,Lroot=root<<1;

     int RL=LR+1,RR=R,Rroot=Lroot|1;

     if (L==R) st_min[root]=C[L];

     else

     {

         build(LL,LR,Lroot);

         build(RL,RR,Rroot);

         st_min[root]=min(st_min[Lroot],st_min[Rroot]);

     }

     //printf(“[%d,%d] min:%d\n”,L,R,st_min[root]);

}

void update(int L,int R,int root)

{

     int LL=L,LR=(L+R)>>1,Lroot=root<<1;

     int RL=LR+1,RR=R,Rroot=Lroot|1;

     st_cnt[Lroot]+=st_cnt[root];

     st_min[Lroot]-=st_cnt[root];

     st_cnt[Rroot]+=st_cnt[root];

     st_min[Rroot]-=st_cnt[root];

     st_cnt[root]=0;

}

int ask(int l,int r,int L,int R,int root=1)

{

    if (l>R||r<L) return oo;

    if (l<=L&&R<=r) return st_min[root];

    int LL=L,LR=(L+R)>>1,Lroot=root<<1;

    int RL=LR+1,RR=R,Rroot=Lroot|1;

    update(L,R,root);

    return min(ask(l,r,LL,LR,Lroot),ask(l,r,RL,RR,Rroot));

}

void insert(int l,int r,int L,int R,int inc=1,int root=1)

{

     if (l>R||r<L) return;

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

     {

        st_cnt[root]+=inc;

        st_min[root]-=inc;

        return;

     }

     int LL=L,LR=(L+R)>>1,Lroot=root<<1;

     int RL=LR+1,RR=R,Rroot=Lroot|1;

     update(L,R,root);

     insert(l,r,LL,LR,inc,Lroot);

     insert(l,r,RL,RR,inc,Rroot);

     st_min[root]=min(st_min[Lroot],st_min[Rroot]);

}

 

int main()

{

    freopen(“balloc.in”,“r”,stdin);

    freopen(“balloc.out”,“w”,stdout);

    scanf(“%d %d\n”,&N,&M);

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

        scanf(“%d\n”,&C[i]);

    for (int i=0;i<M;i++)

        scanf(“%d %d\n”,&A[i],&B[i]);

   

    build(1,N);

    quick_sort(0,M-1);

    for (int i=M-1;i>=0;i–)

        if (ask(A[i],B[i],1,N))

           answer++,insert(A[i],B[i],1,N);

   

    printf(“%d\n”,answer);

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注