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;
}