首页 > 试题广场 >

数组同构

[编程题]数组同构

热度指数：628 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 定义变换函数：
$\hspace{23pt}\bullet\,$ 将一个正整数 $x$ 用其二进制表示中 $1$ 的个数替换，记作 $g(x)$ （即 $\operatorname{popcount}$ ）；
$\hspace{15pt}$ 给定两个长度均为 $n$ 的正整数数组 $A$ 和 $B$ ；
$\hspace{15pt}$ 你可以对 $A$ 或 $B$ 中的任意元素反复执行以下操作，每次操作计数 $1$ ：
$\hspace{23pt}\bullet\,$ 将该元素 $x$ 替换为 $g(x)$ ；

$\hspace{15pt}$ 当且仅当存在置换 $\pi$ ，使得对所有 $1\leqq i\leqq n$ 都有 $A_i = B_{\pi(i)}$ ，也就是两个数组都排序后完全相同，我们称 $A$ 与 $B$ 同构。请计算使 $A$ 与 $B$ 同构所需的最少操作次数。

$\hspace{15pt}$ 可以证明题目一定有解。

输入描述:

第一行输入一个整数 ，表示测试用例数； 
每个测试用例输入格式如下： 
第一行输入一个整数 ； 
第二行输入  个整数 ； 
第三行输入  个整数 ； 
保证所有测试用例中 。

输出描述:

对于每个测试用例，输出一行整数——使  与  同构的最少操作次数。

示例1

输入

输出

2
1

说明

初始时，； 
对  中元素  执行一次变换，得到 ，此时 ； 
对  中一个元素  执行一次变换，得到 ，此时 ； 
此时两数组的元素可以一一匹配，故最少操作数为 。 

在第二个测试用例中：仅需将  中的  变换为 ，得到 ，与  相同，操作数为 。

算法知识视频讲解

群山之中

#include <bits/stdc++.h>
using namespace std;

unsigned long long popcount(unsigned long long x) { return __builtin_popcount(x); }

unsigned long long maxx=0;

unsigned long long process(unordered_map<unsigned long long,unsigned long long>& a, unordered_map<unsigned long long,unsigned long long>& b, unsigned long long thread){
    // 匹配减少
    for(auto it = a.begin(); it != a.end(); ) {
        unsigned long long num = it->first, cnt = it->second;
        if(b.count(num)){
            unsigned long long minus = min(cnt, b[num]);
            it->second -= minus;
            b[num] -= minus;
            if(b[num] == 0) b.erase(num);
            if(it->second == 0) it = a.erase(it);  // 使用迭代器
            else ++it;
        } else {
            ++it;
        }
    }

    unsigned long long res = 0;

    // popcount操作
    for(auto it = a.begin(); it != a.end(); ) {
        unsigned long long num = it->first, cnt = it->second;
        if(num >= thread){
            res += cnt;
            it = a.erase(it);  // 使用迭代器
            unsigned long long newNum = popcount(num);
            a[newNum] += cnt;  // 可以直接累加
            maxx=max(maxx,newNum);
        } else {
            ++it;
            maxx=max(maxx,num);
        }
    }

    for(auto it = b.begin(); it != b.end(); ) {
        unsigned long long num = it->first, cnt = it->second;
        if(num >= thread){
            res += cnt;
            it = b.erase(it);  // 使用迭代器
            unsigned long long newNum = popcount(num);
            b[newNum] += cnt;
            maxx=max(maxx,newNum);
        } else {
            ++it;
            maxx=max(maxx,num);
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long t;
    cin >> t;
    while(t--) {
        unsigned long long n;
        cin >> n;
        unordered_map<unsigned long long,unsigned long long> cntA,cntB;
        
        maxx=-1;
        for(unsigned long long i=0;i<n;++i){
            unsigned long long temp;
            cin>>temp;
            if(cntA.count(temp)){
                cntA[temp]++;
            }else{
                cntA[temp]=1;
            }
            maxx=max(maxx,temp);
        }
        for(unsigned long long i=0;i<n;++i){
            unsigned long long temp;
            cin>>temp;
            if(cntB.count(temp)){
                cntB[temp]++;
            }else{
                cntB[temp]=1;
            }
            maxx=max(maxx,temp);
        }

        unsigned long long ops = 0;

        // 去重
        vector<unsigned long long> threads={21,5,3,2,0};
        for(unsigned long long i:threads){
            if(maxx>=i){
                maxx=0;
                ops += process(cntA,cntB,i);
            }else{
                continue;
            }
        }

        cout << ops << "\n";
    }
}

求路过大神看一看，上述代码可以通过4/20用例，错的情况比预期高。

我的思路是，逐层处理，例如thread=5,对大于等于5的数，做一次popcount（结果会是1/2/3/4），小于5的数就先不管。这样一来，所有的数都来到了[1,4]，下一轮开始时，先去重。再对剩下的，按新阈值3处理。

编辑于 2025-09-16 21:25:25 回复(0)

提交观点

问题信息

贪心位运算堆

难度：

1条回答 24收藏 131浏览

数组同构

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题