题目大意:
给你两个序列a,b,要你从b中找一个排列,使得bi oxr ai 最小,并且字典序最小。
思路:
先把要排列的b插入字典树中去,然后枚举a,一个一个去贪心的找最小值就行了。
每次找的都是最小的xor值就保证了字典序最小。
因为每个数只能被找一次,所以这个题难度在于,从字典树找最小异或值,并且每个数只能被找一次。
最小异或值比较简单,贪心找,当前二进制为0就往0子树走,为1就往1走,实在走不了就计算异或值。
每个数只能走一次,可以用一个数组记录每个节点被插入的次数,然后这题就没了。
代码:
#include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int maxn = 2e7 + 10; typedef long long int ll; int trie[maxn][2],tot; int a[300100]; int cnt[maxn]; void insert(int x){ int p = 0; for(int i = 30; i >= 0; i--){ int c = (x >> i) & 1; if(!trie[p][c])trie[p][c] = ++tot; p = trie[p][c];cnt[p]++; } } int query(int x){ int p = 0,res = 0; for(int i = 30; i >= 0; i--){ int c = (x >> i) & 1; if(trie[p][c] && cnt[trie[p][c]] >= 1)p = trie[p][c]; else p = trie[p][c ^ 1],res |= (1 << i); cnt[p]--; } return res; } void solved(){ int n;cin>>n; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i = 1; i <= n; i++){ int p;cin>>p;insert(p); } for(int i = 1; i <= n; i++){ printf("%d ",query(a[i])); } } int main(){ solved(); return 0; }