题目简述
给定两个长度为 $n$ 的数列 $a,b$,再给定一个数 $x$,请你判断是否存在一种重排 $b$ 数列的方式,使得满足 $a_i>b_i$ 的 $i$ 恰好有 $x$ 个。
$n\leq 2\times 10^5$。
题目分析
遇到这种可行性问题,首先考虑做出最优解,以此来判断是否无解。
接下来,可以思考最优解如何构造,我们利用贪心思想,将 $a$ 数组中的前 $x$ 大的数与 $b$ 数组中的前 $x$ 小的数匹配在一起,判断能否满足这 $x$ 对数都是 $a_i>b_i$ 的。这样做的目的是尽量消耗 $a$ 数组中大的数,保存 $b$ 数组中较大的数,争取接下来 $n-x$ 个数满足 $a_i\leq b_i$。然后,我们判断剩余的数能否满足条件。如果上述两部分数都能满足条件,那便是可行,否则由于最优解都不可行,那一定是无解。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,b[N],x,ans[N];
struct Num
{
int num,id;
}a[N];
bool cmp1(Num i,Num j)
{
return i.num>j.num;
}
bool cmp2(Num i,Num j)
{
return i.num<j.num;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
int f=0;
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i].num;
a[i].id=i;
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
sort(a+1,a+1+n,cmp1);
sort(b+1,b+1+n);
sort(a+1,a+1+x,cmp2);
for(int i=1;i<=x;i++)
{
if(a[i].num>b[i])
{
ans[a[i].id]=b[i];
}
else f=1;
}
sort(a+x+1,a+1+n,cmp2);
for(int i=x+1;i<=n;i++)
{
if(a[i].num<=b[i])
{
ans[a[i].id]=b[i];
}
else f=1;
}
if(f==1)
{
cout<<"No\n";
}
else
{
cout<<"Yes\n";
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
}
}
return 0;
}
标签:sort,cmp2,Arrays,题解,id,int,num,Num,Matching
From: https://www.cnblogs.com/zhuluoan/p/18092280