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

Cutest_Junior · 2020-10-01 23:21:29 · 题解

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

题意

• 点和区间一一匹配（点在区间中）；
• 求最多能匹配上的对数。

贪心

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

证明

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

目前已知：

若 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。

代码来自@zzl_05

#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