【二维偏序+双指针】ABC245 E

女爷i 2024-03-17 14:41 80阅读 0赞

[E - Wrapping Chocolate (atcoder.jp)][E - Wrapping Chocolate _atcoder.jp]

题意：

![761342e888aa45f3bd4f7d93eb714b16.png][]

思路：

因为两个数组都是无序的，因此可以考虑给这两个数组都排个序

将物品和盒子都按照两个维度去排序

我们可以先去枚举物品，然后去选对应的盒子

在选盒子的过程中，注意到 j 具有单调性，因此我们可以双指针

这类双指针可以概括为：对于枚举的量(i)，将合法解放入容器中，再在容器（合法解空间）中找最优解（这里可以贪心），满足的条件通常是二维偏序，一维来保证合法性，另一维来贪心获得最优解

对于这道题，我们可以以长度来check合法性，然后在合法解空间中找出最合适的，即找出第一个宽度>=物品的宽度的盒子，这个可以lower\_bound来解决

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    struct item{
    	int a,b;
    }p[mxn];
    
    struct box{
    	int c,d;
    }q[mxn];
    
    int N,M;
    int a[mxn],b[mxn],c[mxn],d[mxn];
    
    bool cmp1(item x,item y){
    	if(x.a==y.a) return x.b>y.b;
    	return x.a>y.a;
    }
    bool cmp2(box x,box y){
    	if(x.c==y.c) return x.d>y.d;
    	return x.c>y.c;
    }
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=N;i++) cin>>p[i].a;
    	for(int i=1;i<=N;i++) cin>>p[i].b;
    	for(int i=1;i<=M;i++) cin>>q[i].c;
    	for(int i=1;i<=M;i++) cin>>q[i].d;
    	sort(p+1,p+1+N,cmp1);
    	sort(q+1,q+1+M,cmp2);
    	int j=1;
    	multiset<int> S;
    	for(int i=1;i<=N;i++){
    		while(j<=M&&p[i].a<=q[j].c){
    			S.insert(q[j].d);
    			j++;
    		}
    		//cout<<i<<" "<<j<<'\n';
    		auto it=S.lower_bound(p[i].b);
    		if(it==S.end()){
    			cout<<"No"<<'\n';
    			return;
    		}
    		S.erase(it);
    	}
    	cout<<"Yes"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

还有一道类似的题，前几天刚做过：

[(135条消息) 【贪心+双指针】ABC308 F\_lamentropetion的博客-CSDN博客][135_ _ABC308 F_lamentropetion_-CSDN]

[E - Wrapping Chocolate _atcoder.jp]: https://atcoder.jp/contests/abc245/tasks/abc245_e
[761342e888aa45f3bd4f7d93eb714b16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cd10307927584970a36d8d62c29c74c7.png
[135_ _ABC308 F_lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/131503394