bzoj 4995 [Usaco2017 Feb]Why Did the Cow Cross the Road

​​http://www.elijahqi.win/archives/3200​​​

題目描述

Farmer John’s cows are trying to learn to cross the road effectively. Remembering the old “why did the chicken cross the road?” joke, they figure the chickens must be experts on crossing the road, and go off in search of chickens to help them.

農夫約翰的牛們正在嘗試去學會高效地穿越馬路。熟知經典的笑話“為什麼雞要過馬路？”，他們想到雞一定是過馬路的專家，便動身尋找能夠幫助它們的雞。

As it turns out, chickens are very busy creatures and have limited time to help the cows. There are

C

C chickens on the farm (

1 \leq C \leq 20,000

1≤C≤20,000 ), conveniently numbered

1 \ldots C

1…C , and each chicken

i

i is only willing to help a cow at precisely time

T_i

Ti​ . The cows, never in a hurry, have more flexibility in their schedules. There are

N

N cows on the farm (

1 \leq N \leq 20,000

1≤N≤20,000 ), conveniently numbered

1 \ldots N

1…N , where cow

j

j is able to cross the road between time

A_j

Aj​ and time

B_j

Bj​ . Figuring the “buddy system” is the best way to proceed, each cow

j

j would ideally like to find a chicken

i

i to help her cross the road; in order for their schedules to be compatible,

i

i and

j

j must satisfy

A_j \leq T_i \leq B_j

Aj​≤Ti​≤Bj​ .

牛們發現，雞是一種特别繁忙的動物，并且隻有一定的時間來幫助它們。農場上共有

C

C 隻雞（

1\le C\le 20000

1≤C≤20000 ），十分便利地被編号為

1…C

1…C , 而且，每隻雞

i

i 隻有恰好在時間

T_{i}

Ti​ 時才會願意幫助牛們。而從不慌張的牛們，有更加靈活的時間安排。農場上共有

N

N 隻牛（

1\le N\le 20000

1≤N≤20000 ），也十分便利地被編号為

1…N

1…N ，牛

j

j 在時間

A_{j}

Aj​ 到

B_{j}

Bj​ 之間可以穿過馬路。想到“小夥伴系統”是最好的行進方式，每隻牛

j

j 會理想地願意找到一隻雞

i

i 來幫助她穿過馬路；為了是它們的時間表不沖突，

i

i 和

j

j 必須滿足

A_{j}\le T_{i}\le B_{j}

Aj​≤Ti​≤Bj​

If each cow can be paired with at most one chicken and each chicken with at most one cow, please help compute the maximum number of cow-chicken pairs that can be constructed.

如果每頭奶牛最多隻能配一隻雞，而每隻雞最多隻配上一頭牛，請幫忙計算出可以構造的牛雞對的最大數量。

輸入輸出格式

輸入格式：

The first line of input contains

C

C and

N

N . The next

C

C lines contain

T_1 \ldots T_C

T1​…TC​ , and the next

N

N lines contain

A_j

Aj​ and

B_j

Bj​ (

A_j \leq B_j

Aj​≤Bj​ ) for

j = 1 \ldots N

j=1…N . The

A

A ‘s,

B

B ‘s, and

T

T ‘s are all non-negative integers (not necessarily distinct) of size at most 1,000,000,000

第一行的輸入包括

C

C 和

N

N 。下面的

C

C 行包括

T1…TC

T1…TC ，再接下來的

N

N 行包括

A_{j}

Aj​ 和

B_{j}

Bj​ (

A_{j}\le B_{j}

Aj​≤Bj​ )，

j=1…N

j=1…N 。所有

A,B

A,B 與

T

T 都是非負整數（可能相等），并皆小于等于

1,000,000,000

1,000,000,000 。

輸出格式：

Please compute the maximum possible number of cow-chicken pairs.

請計算最大的可行牛-雞配對數。

輸入輸出樣例

輸入樣例#1： 複制

5 4

7

8

6

2

9

2 5

4 9

0 3

8 13

輸出樣例#1： 複制

3

ss

考慮将線段按照右端點遞增的順序排列相同情況下按照左端點排列 然後

#include<set>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=2e4+10;
multiset<int>s;
multiset<int>::iterator it;
struct node{int l,r;}line[N];int n,m,ans;
inline bool cmp(const node &a,const node &b){return a.r==b.r?a.l<b.l:a.r<b.r;}
int main(){
    freopen("bzoj4995.in","r",stdin);
    m=read();n=read();
    for (int i=1;i<=m;++i) s.insert(read());
    for (int i=1;i<=n;++i) line[i].l=read(),line[i].r=read();
    sort(line+1,line+n+1,cmp);it=s.begin();
    for (int i=1;i<=n;++i){
        it=s.lower_bound(line[i].l);
        if (it!=s.end()&&*it<=line[i].r) ++ans,s.erase(it),it=s.begin();
    }printf("%d\n",ans);
    return 0;
}