自动搬运

查看原文

来自洛谷，原作者为

	Cutest_Junior 平平淡淡才是真

搬运于2025-08-24 21:51:21，当前版本为作者最后更新于2020-10-01 23:21:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解 P3661 【[USACO17FEB]Why Did the Cow Cross the Road I S】

题意

• $m$ 个点，$n$ 个区间（闭区间）；
• 点和区间一一匹配（点在区间中）；
• 求最多能匹配上的对数。

贪心

1. 对区间按右端点的位置升序排列；
2. 对于每个区间，找到位置最小的还没匹配的点，相互匹配。
3. 统计对数。

证明

设有两个区间 $\left[l1,r1\right]$，$\left[l2,r2\right]$，有两个点被第一个区间包含 $d1,d2$。

目前已知：

1. $r1\le r2$ （已排序）；
2. $l1\le d1<d2\le r1$。

若 $l2<d1$:

任意两个都可以相互匹配，第一个区间选哪个都不影响结果。

若 $d1\le l2\le d2$：

第二个区间只能与 $d2$ 匹配，第一个区间与 $d1$ 匹配更优。

若 $d2<l2$：

第二个区间无法匹配，第一个区间选哪个都不影响结果。

综上所述，第一个区间与较小的点匹配，一定不会更劣。

代码

# include <cstdio>
# include <algorithm>

using namespace std ;

const int N = 20005 ;

int chicken [ N ] ;
bool visit [ N ] ;

struct Cow
{
    int l , r ;
};

bool operator < ( Cow a , Cow b ) // 按右端点升序排序
{
    return a . r < b . r ;
}

Cow cow [ N ] ;

int read ( ) // 事实上在本题优化不大，但还是加上
{
    int a = 0 ;
    char c = getchar ( ) ;
    
    while ( c < '0' || c > '9' )
    {
        c = getchar ( ) ;
    }
    
    while ( c >= '0' && c <= '9' )
    {
        a = a * 10 + c - '0' ;
        c = getchar ( ) ;
    }
    
    return a ;
}

int main ( )
{
    int n = read ( ) , m = read ( ) ;
    
    for ( int i = 1 ; i <= n ; ++ i )
    {
        chicken [ i ] = read ( ) ;
    }
    
    sort ( chicken + 1 , chicken + n + 1 ) ;
    
    for ( int i = 1 ; i <= m ; ++ i )
    {
        cow [ i ] . l = read ( ) ;
        cow [ i ] . r = read ( ) ;
    }
    
    sort ( cow + 1 , cow + m + 1 ) ;
    
    int ans = 0 ;
    
    for ( int i = 1 ; i <= m ; ++ i )
    {
        for ( int j = 1 ; j <= n ; ++ j )
        {
            if ( chicken [ j ] < cow [ i ] . l ) // 还没进区间就下一个
            {
                continue ;
            }
            
            if ( chicken [ j ] > cow [ i ] . r ) // 过了区间就直接结束
            {
                break ;
            }
            
            if ( visit [ j ] ) // 因为要一一对应，已经匹配过的就不能再匹配了
            {
                continue ;
            }
            
            ++ ans ;
            visit [ j ] = 1 ;
            break ;
        }
    }
    
    printf ( "%d" , ans ) ;
}

上述做法跑了 $1.76s$。

极慢极慢。

然后某学长给我提供了一个 $O\left(N\log N\right)$ 的做法。

$O\left(N\log N\right)$ 做法

由于点是有序的，那么就可以用二分进行优化。

但是，一个区间内的点理论上有也 $n$ 个，如果前 $n-1$ 个点都被选过，则这个算法就又退化回 $O\left(N^2\right)$ 了。

考虑选完就删点，但是数组删点复杂度为 $O\left(N\right)$，于是又退化回$O\left(N^2\right)$ 了。（我太难了）

考虑数据结构优化，需要一个数据结构，可以保持数据有序，可以二分，可以在 $O\left(\log N\right)$ 时间内删点。

某学长想出了 STL 里的 multiset。

代码来自

#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define ll long long
#define ri register int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
inline int read() {
	ri v = getchar();int f = 1,t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	return t *= f;
}

const int N = 20010;

//1.区间排序，对于每个r_i找一个最近的前面的点x_j，如果x_j<l_i，就肯定不行，反之行，也弹掉
multiset <int> s;

struct inter {
    int l,r;
    friend inline bool operator < (const inter & a,const inter &b) {
        return a.r == b.r ? a.l > b.l : a.r < b.r;
    }
}a[N];

int n,m,x[N],ans;
multiset<int>::iterator it;

signed main() {
    n = read(),m = read();
    for (int i = 1;i <= n;++i) x[i] = read(),s.insert(x[i]);
    for (int i = 1;i <= m;++i) a[i].l = read(),a[i].r = read();
    sort(a+1,a+1+m);
    //for (int i = 1;i <= m;++i) printf("%d %d\n",a[i].l,a[i].r);
    for (int i = 1;i <= m;++i) {
        it = s.lower_bound(a[i].l);
        //printf("%d\n",*it);
        if (it != s.end()) {
            if (*it <= a[i].r) ++ans,s.erase(it);
        }
    }
    printf("%d\n",ans);
	return 0;
}

update

$2020.10.1$ 初稿。

$2020.10.21$ 修改如下。

in 《证明》。

目前已知：

1. $r1\le r2$ （已排序）；
2. $l1\le d1<d2\le r1$。

原来写成：

目前已知：

1. $r1\le r2$ （已排序）；
2. $r1\le d1<d2\le r1$。

已修改。(感谢

https://www.luogu.com.cn/user/105230

---

添加《$O\left(N\log N\right)$ 做法》一部分。（感谢

https://www.luogu.com.cn/user/105230

非常抱歉在短时间内提交两次题解，还望管理大大通过。