codeforce每日一题链接
题目链接
题目描述
给定数字$n,k$,在给定两个长度为$n$的数组$a,b$,请你重新排列$b$,使得$|a[i]-b[i]|<=k$。题目保证有解。
样例
输入样例1
3
5 2
1 3 5 3 9
2 5 11 2 4
6 1
-1 3 -2 0 -5 -1
-4 0 -1 4 0 0
3 3
7 7 7
9 4 8
输出样例1
2 2 5 4 11
0 4 -1 0 -4 0
8 4 9
算法
(排序+贪心) $O(n*log(n))$
题目保证有解,我们可以对a排序,在对b排序,我们发现,a[0]和b[0]一定满足,因为题目保证有解。可以证明,如果a[0]和b[0]不满足,那么a数组往后和b数组往后的数字差会越来越大,所以更不可能满足。所以a,b排序后一一匹配就好了。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int a[N], b[N], c[N];
int res[N];
inline void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) c[i] = i;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
sort(c+1, c+n+1,[&](int x, int y){
return a[x]<a[y];
});
sort(b+1, b+n+1);
for(int i=1;i<=n;i++) res[c[i]] = b[i];
for(int i=1;i<=n;i++) cout<<res[i]<<" ";
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}