SP3943 MDOLLS - Nested Dolls 题解

rainbow_cat · 2023-09-10 11:01:52 · 题解

不知道为什么这道题和导弹拦截的第二问类似
处理：结构体：

struct node{int w,h;}a[200010];

主要思路：贪心

贪心策略：我们可以先对于高度和宽度中的一个参数进行排序，那么此时我们就不用对这个参数进行考虑。接下来对于每个娃娃，选择一个娃娃套入，为使解最优，我们选择高比他大的娃娃中高最小的（可以理解为让剩余的空间尽可能的大）。为了避免超时，我们可以使用二分算法进行优化：

while(l<r)//二分模版
{
    int mid=(l+r)/2;
    if(h[mid]<=a[i].h)l=mid+1;
    else r=mid;
}       

在找到合适的娃娃后更新他的高度：h[l]=a[i].h;
如果没有合适的娃娃则独自成为一个娃娃：if(h[ans]<=a[i].h)h[++ans]=a[i].h;
（注意：由于是多组答案所以数组与答案要进行清空！！！）
——————————————————————分割线———————————————————————
完整代码：

#include<bits/stdc++.h>
using namespace std;
struct node{int h,w;}a[200010];//定义结构体
int t,n,h[200010],ans;//h[i]代表每个套娃的高度
bool cmp(node x,node y)
{
    if(x.w!=y.w)return x.w<y.w;//这里选择先按宽度排序
    return x.h>y.h;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        ans=0;
        memset(h,0,sizeof(h));//清空
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i].w>>a[i].h;//输入，先宽后高
        sort(a+1,a+n+1,cmp);
        for(int i=n;i>=1;i--)
        {
            if(h[ans]<=a[i].h)h[++ans]=a[i].h;
            else
            {
                int l=1,r=ans;
                while(l<r)//二分
                {
                    int mid=(l+r)/2;
                    if(h[mid]<=a[i].h)l=mid+1;
                    else r=mid;
                }            
                h[l]=a[i].h;//更新高度
            }
        }
        cout<<ans<<'\n';//输出要加换行    
    }   
    return 0;
}