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

K_add_HCl_add_F2 · 2026-07-23 11:20:28 · 题解

题意

已经很清楚了，不讲。

具体怎么做

考虑贪心。设最多可以展出 x 幅画。

这 x 幅画所用的画框一定是用最大的 x 个画框。

对于画而言，因为还有一个美观度的限制，所以大的画框一定要装美观度尽可能大的画。对于美观度相同的一些画，显然将较大的画装入较大的画框中。

:::info[证明]

• 更大的画框能装的画一定不会更少，所以最大的 x 个画框更容易符合条件地装下 x 幅画。

• 若美观度最大的画被装入较小的画框中，则比这个画框更大的画框就一定会被浪费，不优于将美观度最大的画装入最大的画框，这样就没有画框被浪费。

• 对于两个美观度相同的画，若将较小的画装入较大的画框中，则较大的画可能装不下，不优于将大的画装入大的画框。

:::

因此，画框要从大到小排序，画以美观度为第一关键字，大小为第二关键字从大到小排序。

用双指针维护贪心过程。设当前尝试第 i 大的画框匹配第 j 幅画。若因画太大而匹配失败，则 j\gets j+1 并重新匹配。若匹配成功，则 ans\gets ans+1,i\gets i+1,j\gets j+1。

:::success[正确代码]

#include<bits/stdc++.h>
using namespace std;
struct picture{int s,v;}a[114514];
int n,m,c[114514],ans;
bool cmp(picture a,picture b){return a.v==b.v?a.s>b.s:a.v>b.v;}
bool cmp2(int a,int b){return a>b;}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;scanf("%d%d",&a[i].s,&a[i].v),++i);
    for(int i=1;i<=m;scanf("%d",&c[i]),++i);
    sort(a+1,a+n+1,cmp);sort(c+1,c+m+1,cmp2);
    for(int i=1,j=1;i<=m&&j<=n;++j)if(c[i]>=a[j].s)++ans,++i;
    printf("%d",ans);
}

:::