首页 > 试题广场 >

数组同构

[编程题]数组同构

热度指数：876 时间限制：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;
int cntOfOne(long long num) {
    int cnt = 0;
    //需要确保num的二进制不会有64个1
    while (num) {
        if (num & 1) {
            cnt++;
        }
        num = num >> 1;
    }
    return cnt;
}
int main() {
    //所有数 -> [1,63] -> [1,6] -> [1,2]
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;int tt=t;
    while (tt--) {
        int n;
        cin >> n;
        
        vector<long long> num1(n, 0);
        vector<long long> num2(n, 0);
        for (int i = 0; i < n; i++) {
            cin >> num1[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> num2[i];
        }
        

        int ans = 0;
        int cnt[64]; memset(cnt, 0, sizeof(cnt));

        unordered_map<long long, int> mp;
        for (int i = 0; i < n; i++) {
            mp[num1[i]]++;
            mp[num2[i]]--;
        }
        for (auto num : mp) {
            if (num.second > 0) {
                if (num.first > 63) {
                    ans+=num.second;
                    cnt[cntOfOne(num.first)]+=num.second;
                }
                else {
                    cnt[num.first]+= num.second;
                }
            }
            else if(num.second < 0){
                if (num.first > 63) {
                    ans+=(-num.second);
                    cnt[cntOfOne(num.first)]+= num.second;
                }
                else {
                    cnt[num.first]+= num.second;
                }
            }
        }
       //if(t==11){ for(auto n:cnt)cout<<n<<" ";cout<<endl;}
        int cnt2[7]; memset(cnt2, 0, sizeof(cnt2));

        for (int i = 1; i < 64; i++) {
            if (cnt[i] > 0) {
                if (i > 6) {
                    cnt2[cntOfOne(i)]+=cnt[i];
                     ans+=cnt[i];
                }
                else {
                    cnt2[i]+=cnt[i];
                }
            }
            else if (cnt[i] < 0) {
                if (i > 6) {
                    cnt2[cntOfOne(i)]+=cnt[i];
                    ans+=(-cnt[i]);
                }
                else {
                    cnt2[i]+=cnt[i];
                }
            }
        }
        //for(auto n:cnt2)cout<<n<<" ";cout<<endl;
        int cnt3[3] = { 0,0,0 };
        for (int i = 1; i < 7; i++) {
            if (cnt2[i] > 0) {
                if (i > 2) {
                    ans += cnt2[i];
                    cnt3[cntOfOne(i)] += cnt2[i];
                }
                else {
                    cnt3[i] += cnt2[i];
                }
            }
            else if (cnt2[i] < 0) {
                if (i > 2) {
                    ans += (-cnt2[i]);
                    cnt3[cntOfOne(i)] += cnt2[i];
                }
                else {
                    cnt3[i] += cnt2[i];
                }
            }
        }
        //for(auto n:cnt3)cout<<n<<" ";cout<<endl;
        ans += abs(cnt3[1]);
       
        cout << ans << endl;

    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-09-19 22:06:55 回复(0)

群山之中

#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)

提交观点

问题信息

贪心位运算堆

难度：

2条回答 35收藏 548浏览

数组同构

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题