P11789 [JOI 2019 Final] 画展 / Exhibition题解

不知为何没人发题解。

思路

• 第一眼肯定是贪心。
• 显然可以先把所有的画以美观值和大小为第一，第二关键字从小到大排序，因为为了先保证美观满足条件，再对画框大小的限制进行贪心。
• 然后从后往前枚举，先匹配大的画框,再用剩下的匹配小的画框。容易证明大的画框也一定能装下小的画，肯定不会更劣。
• 然后你就能完成这道题啦！

代码+解释

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m;
pair<int, int> a[N];
int b[N];
int ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].second >> a[i].first;//倒着输入，因为美观是第一关键字，大小是第二关键字
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
    }
    sort(a, a + n);//利用pair自带的排序
    sort(b, b + m);

    for (int i = n - 1, j = m - 1; i >= 0 && j >= 0; i--)//从后往前
    {
        if (b[j] >= a[i].second)//如果匹配的上就更新答案，并和下一个匹配
        {
            ans++;
            j--;
        }
    }

    cout << ans;//输出答案
    return 0;
}