P8109 [Cnoi2021]幻想乡程序设计大赛 题解

· · 题解

没有题解来凑热闹。

考虑每个颜色的气球给哪一个组。

题面里说了序列不降，我们要利用这个条件。

按气球数从大到小考虑。

假如这个颜色气球的数量多于任意一个组的人数，要最多只能给人数最多的组。

假如给了较少的组，那么下一个颜色数量比他小，无论给哪个都不会更优。

否则呢？随便选一个大于他的就能用上全部气球，因为下一个颜色的气球数量更少，所以现在随便即可。

既然随便，那为何不选最多的？

总结一下，按气球数从大到小，每次选一个最大的组。

等于组也从大到小。

也就是按照排名一一匹配。

#include<bits/stdc++.h>
using namespace std;
int n,a[100008],b[100008],ans; 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        ans+=min(a[i],b[i]); 
    }
    cout<<ans<<endl;
    return 0;
}