noip模拟赛水题

题目描述

LYK出了道水题。

这个水题是这样的：有两副牌，每副牌都有n张。

对于第一副牌的每张牌长和宽分别是xi和yi。对于第二副牌的每张牌长和宽分别是aj和bj。第一副牌的第i张牌能覆盖第二副牌的第j张牌当且仅当xi>=aj并且yi>=bj。（注意牌不能翻转）当然一张牌只能去覆盖最多一张牌，而不能覆盖好多张。

LYK想让两副牌的各n张一一对应叠起来。它想知道第二副牌最多有几张能被第一副牌所覆盖。

输入格式(water.in)

第一行一个数n。

接下来n行，每行两个数xi,yi。

接下来n行，每行两个数aj,bj。

输出格式(water.out)

输出一个数表示答案。

输入样例

2 3

5 7

6 8

4 1

2 5

3 4

输出样例

数据范围

对于50%的数据n<=10。

对于80%的数据n<=1000。

对于100%的数据1<=n<=100000，1<=xi,yi,aj,bj<=10^9。

分析：一眼贪心题，覆盖的两张牌肯定是要让它们的x,y的差值尽量小才是最优的，因为这样就把更多的选择留给了其它的牌.那么先把所有牌按照x从小到大排序，然后在第二副牌中把a[j] <= x[i]的牌的b放进一个multiset中，每次取与y[i]最相近的一个b值即可.

multiset是一个可重复的set,里面的元素都是排好序的，upper_bound的返回看multiset中数的情况而定，如果upper_bound(a[i]),multiset中存在了a[i],就返回所有a[i]中最后面一个的迭代器，如果不存在，就返回第一个大于a[i]的迭代器,因为要求<=的嘛，方便起见迭代器减一下就好了.

#include <set>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

struct node

{

    int x, y;

}a[],b[];

int n, k, ans;

bool cmp(node a, node b)

{

    if (a.x == b.x)

        return a.y < b.y;

    return a.x < b.x;

}

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

        scanf("%d%d", &a[i].x, &a[i].y);

    for (int i = ; i <= n; i++)

        scanf("%d%d", &b[i].x, &b[i].y);

    sort(a + , a +  + n, cmp);

    sort(b + , b +  + n, cmp);

    multiset <int> s;

    k = ;

    for (int i = ; i <= n; i++)

    {

        while (k <= n && a[i].x >= b[k].x)

        {

            s.insert(b[k].y);

            k++;

        }

        multiset <int>::iterator it = s.upper_bound(a[i].y);

        if (it == s.begin())

            continue;

        it--;

        s.erase(it);

        ans++;

    }

    printf("%d\n", ans);

    return ;

}

巴特西

noip模拟赛水题

最新文章

热门文章

巴特西

noip模拟赛 水题

最新文章

热门文章

noip模拟赛水题