Problem

你将举办一个画展，在展览中，你需要将一些画放入一些画框中并摆放成一排。

展览有\(N\)幅候选画，编号从\(1\)到\(N\)。画具有大小\(S_i\)和美观度\(V_j\)。

另外，有\(M\)个候选画框，编号从\(1\)到\(M\)。画框\(j(1\le j \le M)\)的大小为\(C_j\)。

只有大小不超过\(C_j\)的画才能放入画框\(j\)中。每个画框中最多只能放一幅画。每幅要展出的画都必须放在一个画框中。

考虑到美观因素，展出的画必须满足以下条件：

• 对于任意两幅相邻的画，右边的画框大小不小于左边的画框

• 对于任意两幅相邻的画，右边的画的美观度不小于左边的画的美观度

你需要求出你最多能展出多少幅画。

原题题面戳这里。

Solution

考虑贪心，尝试满足条件的情况下构造答案。

首先先对画框的大小排序，这样我们就可以满足条件\(1\)了。

然后再考虑怎样把画装进画框，为了使答案满足条件\(2\)，我们还要要求画的美观度排序。

考虑怎样才是最优解，很明显，为了使画展出最多，我们要尽量先考虑美观度大的画，才能使剩下的可以展出的画更多，而不是先放美观度小的画导致剩下的画不能放，这样在保证题目要求的前提下，又保证了更优的答案。

接着考虑如果美观度一样怎么办？同样的，为了满足最优解，就不能浪费画框，如果我们先选择小的画同样可能导致画框被浪费，大的画装不进去。

举个栗子：

现在我们有\(3\)个画框和\(5\)张画：

先只考虑美观度，如果我们把第\(2\)张画放到第\(1\)个画框里：

那么第\(3\)个画框就浪费了，因为没有美观度比\(1\)低的画了（这里把条件\(2\)颠倒了一下，但本质上是没有区别的），如果把第\(1\)个画放到画框\(1\)，那甚至更糟，画框\(2,3\)都浪费了（紫色），所以我们优先放美观度大的画（黑色）：

再考虑大小，如果我们先放小的：

为满足题目要求，同样浪费了两个画框，但如果先放大的就不一样：

这样没有浪费，只是因为迫不得已才只能装\(2\)幅画。

于是这样我们就得出了一个比较优解，但注意画的大小还有限制（就像上图）。

然后再解决大小限制的问题，可以设两个指针\(i\)和\(j\)，代表第\(i\)幅画和第\(j\)个画框，如果\(C_i\le b_j\)代表大小比画框小，可以装的下，反之不行。

如果装的下，\(j\)就指向下一个画框，否则\(i\)指向下一幅画，时间复杂度为\(O (n+m)\)，加上排序，总时间复杂度为\(O(n\log n+m\log m)\)。

当然如果把\(n\)幅画或\(m\)个画框全部装完，那么就是答案了。

注意，我们可以保证这样的顺序一定最优，所以才能扫一遍找出最优解。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int b[N];
struct node {
    int x, y;
} a[N];
bool cmp(node x, node y) {
    if (x.y == y.y)
        return x.x > y.x;

    return x.y > y.y;
}
int main() {
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].x, &a[i].y);

    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);

    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + m + 1);
    int i = 1, j = m;

    while (i <= n && j >= 1) {
        if (b[j] >= a[i].x) {
            ans++;
            j--;
        }

        i++;
    }

    printf("%d", ans);
    return 0;
}

[JOI2018]展覧会