SP3943 MDOLLS - Nested Dolls 题解

~~不知道为什么这道题和导弹拦截的第二问类似~~ 处理：结构体： ```cpp struct node{int w,h;}a[200010]; ``` ### 主要思路：贪心 贪心策略：我们可以先对于高度和宽度中的一个参数进行排序，那么此时我们就不用对这个参数进行考虑。接下来对于每个娃娃，选择一个娃娃套入，为使解最优，我们选择高比他大的娃娃中高最小的（可以理解为让剩余的空间尽可能的大）。为了避免超时，我们可以使用二分算法进行优化： ```cpp 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;``` （注意：由于是多组答案所以数组与答案要进行清空！！！） ——————————————————————分割线——————————————————————— 完整代码： ```cpp #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; } ```