听说没人写,那就来一发。
这种偏序问题大概率是要排个序的。将盒子和巧克力视为一个东西,\(c\) 视为 \(a\),\(d\) 视为 \(b\),放在一起以 \(a\) 为第一关键字,\(b\) 为第二关键字降序排序。此时,我们发现前面的盒子的 \(a\) 值一定是满足后面巧克力的 \(b\) 值的。所以记录还没被用的所有盒子的 \(b\) 值,每次有巧克力就在其中找到其 \(b\) 值的后继,即最小的 \(b'\geq b\) 来装。这样一定是最优的。
再举一个具体一点的例子:
在这种情况下,如果两个盒子都满足,选择 \(2\) 仍然是更优的,因为 \(a\) 的条件两个都一定能满足,\(b\) 却不一定。
用一个 multiset 维护即可。还要注意排序的时候如果有同等大小的巧克力和盒子,盒子要排在前面。
code:
点击查看代码
int n,m;
struct node{
int x,y,op;
}e[N<<1];
multiset<int> st;
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&e[i].x);
e[i].op=1;//要记录是盒子还是巧克力
}
for(int i=1;i<=n;i++){
scanf("%d",&e[i].y);
}
for(int i=n+1;i<=n+m;i++){
scanf("%d",&e[i].x);
}
for(int i=n+1;i<=n+m;i++){
scanf("%d",&e[i].y);
}
sort(e+1,e+n+m+1,[&](node a,node b){return a.x!=b.x?a.x>b.x:(a.y!=b.y?a.y>b.y:a.op<b.op);});
for(int i=1;i<=n+m;i++){
if(e[i].op){
auto it=st.lower_bound(e[i].y);
if(it==st.end()){
puts("No");
return;
}
st.erase(it);
}else{
st.insert(e[i].y);
}
}
puts("Yes");
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)solve();
}