ACM中的M题【牛客tracker 每日一题】
ACM中的M题
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
此题为B BB题的困难版本，与B BB题有是否排序、交换元素限制以及数据范围的不同
有一个长度为n nn的数组{ a i } \{a_i\}{ai}，每个{ a i } \{a_i\}{ai}属于且仅属于一个类别{ b i } \{b_i\}{bi}
已知{ a i } \{a_i\}{ai}无相同元素
你可以多次交换同一个类别下任意2 22个元素
直到每个位置的元素和原来都不相同
若有解请输出最小交换次数，反之无解输出− 1 -1−1
输入描述：
第一行输入一个正整数n nn
第二行输入n nn个非负整数{ a i } \{a_i\}{ai}
第三行输入n nn个非负整数{ b i } \{b_i\}{bi}，表示{ a i } \{a_i\}{ai}类别
1 ≤ n ≤ 2 × 10 5 ; 0 ≤ a i ≤ 2 × 10 9 ; 0 ≤ b i ≤ 2 × 10 9 1≤n≤2×10^5; 0≤a_i≤2×10^9; 0≤b_i≤2×10^91≤n≤2×105;0≤ai≤2×109;0≤bi≤2×109
数据保证无相同a i a_iai
输出描述：
一个整数表示结果
若有解，输出最小交换次数
反之，输出− 1 -1−1
示例1
输入：
3 1 2 3 1 1 1输出：
2说明：
显然3 33个元素属于统一类别
第一次交换第一第二位置变为[ 2 , 1 , 3 ] [2,1,3][2,1,3]
第二次交换第一第三位置变为[ 3 , 1 , 2 ] [3,1,2][3,1,2]
显然无更少的交换次数能满足条件
示例2
输入：
3 0 1 2 0 1 2输出：
-1复制
显然3 33个数类别均不相同不可交换
示例3
输入：
4 0 1 2 3 0 2 2 0输出：
2示例4
输入：
2 1 2 0 0输出：
1解题思路
本题核心是分类别独立构造错排，结合置换环性质求解最小交换次数。由于仅同类别元素可任意交换，不同类别之间互不影响，因此按类别拆分问题独立求解。
首先做合法性判断：若存在大小为1的类别，该元素无法移动，必然留在原位，直接判定无解输出-1。
对于大小为c cc的类别，要让所有元素错位，最少交换次数为⌈ c / 2 ⌉ \lceil c/2 \rceil⌈c/2⌉（即(c+1)//2）：优先用两两交换（2元置换环）最大化环数，奇数个元素时搭配一个3元环补足，此时交换次数最少。
最后累加所有类别的交换次数即为答案。算法时间复杂度O ( n ) O(n)O(n)，完美适配n ≤ 2 × 10 5 n \le 2\times10^5n≤2×105的数据约束。
总结
核心逻辑：按类别拆分问题，每个类别独立构造错排，累加各类别最小交换次数。
关键操作：哈希表统计类别大小、单元素类别判无解、按公式计算每类交换次数。
效率保障：线性遍历统计，常数级公式计算，无冗余运算，轻松处理十万级数据。
代码简要说明
- 输入处理：读取数组长度与元素值（元素值本身不影响结果，仅需类别信息），用哈希表统计每个类别的元素数量。
- 无解判断：遍历哈希表，若存在类别大小为1，直接返回
-1。 - 累加计算：对每个类别计算
(c+1)/2并累加到总答案，最终输出总和。 - 优化说明：使用
unordered_map实现线性统计，全程仅需一次遍历，效率极高。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llsolve(){ll ans=0,n;cin>>n;unordered_map<ll,ll>mp;for(ll i=0;i<n;i++){ll x;cin>>x;}for(ll i=0;i<n;i++){ll x;cin>>x;mp[x]++;}for(auto[_,c]:mp){if(c==1)return-1;ans+=(c+1)/2;}returnans;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cout<<solve()<<endl;return0;}