D. Searchlights 思维 偏序

发布时间 2023-09-14 22:57:18作者: 久远寺冇珠

 Problem - D - Codeforces

 题意:分别给你一个n个pair<a,b>和m个pair<c,d>,问最少操作数,可以使得对于所有的<a,b>,对于任意的<c,d>,都有(a>c)或(b>d)。两个条件满足其一即可。

  操作的定义是,在一次操作中,你可以选a或b,然后对于所有的你选定的,都加1

解法:对于每一个m,我们遍历n来求要满足上述条件的pair,经过m*n次操作,我们得到了一个数组,然后对其以sort,并且删去b元素小于等于最后一个元素不相交的,并不断更新这个值。看图更好理解

我们要删掉图中蓝色和紫的,而保留这个绿色的,因为我们要满足这个绿色时候,一定能满足蓝色和紫色的需求。

然后我们的到了类似于上图这样的pair数组,数字上小下大,我们发现当我们取紫色元素的b时,大家都能被覆盖,当我们取橙色的a时同理。我们发现当我们取一个a后,小于其a的就都不用考虑了,而且b的大小顺序是相反的,所以我们再取一个b,能覆盖剩下的元素就ok了,那么根据贪心,我们肯定取最小的b,而且如果a时按照升序排列的,则b一定按照降序排列,因为要相交。所以我们就取下一个b元素即可。扫一遍取min然后特判两个端点即可

void solve(){
    int n,m;cin>>n>>m;
    vector<pii>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se;
    vector<pii>b;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        for(int i=1;i<=n;i++){
            if(x<a[i].fi||y<a[i].se)continue;
            b.push_back({x-a[i].fi+1ll,y-a[i].se+1ll});
        }
    }
    if(b.size()==0){
        cout<<0<<"\n";return ;
    }
    sort(b.begin(),b.end());
    //for(auto &i:b)cout<<i.fi<<" "<<i.se<<"\n";
    vector<pii>c;
    c.push_back(*(b.end()-1));
    int lt=(b.end()-1)->se;
    for(int i=(int)b.size()-2;i>=0;i--)if(b[i].se>lt){lt=b[i].se;c.push_back(b[i]);}
    n=c.size();
    //for(auto i:c)cout<<i.fi<<" "<<i.se<<"\n";
    int ans=min(c[0].fi,c[n-1].se);
    for(int i=1;i<n;i++){
        ans=min(ans,c[i].fi+c[i-1].se);
    }
    cout<<ans<<"\n";
}