强迫症时间限制1 秒空间限制256 MB知识点枚举、贪心网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述铁子最近犯上了强迫症他总是想要把一个序列里的元素变得两两不同而他每次可以执行一个这样的操作他可以选择序列里的任意两个元素相加不妨记作a aa和b bb然后把a b a bab放进序列里再删掉a aa和b bb其中的随便一个。问最少操作多少次可以完成铁子的愿望输入描述第一行一个整数n nn表示序列的长度( 1 ≤ n ≤ 10 5 ) (1 \le n \le 10^5)(1≤n≤105)。第二行n nn个整数a i a_iai​表示序列的每个整数( 1 ≤ a i ≤ 10 9 ) (1 \le a_i \le 10^9)(1≤ai​≤109)。输出描述输出一行表示答案。示例示例 1输入3 1 2 2输出1说明将序列的第1 11个整数和序列的第2 22个整数相加再删掉第2 22个整数。解题思路本题是最少操作次数使序列元素两两不同的构造题。每次操作可以将任意两个元素相加把和加入序列并删除其中一个原元素目标是让最终序列中没有重复元素。1. 问题等价转化操作效果序列长度始终为n nn。每次操作选择两个元素合并出一个新的“和”同时删除一个旧元素相当于用新值替换掉一个旧值。最少操作次数设初始序列中不同数字的个数为m mm则重复数字的总数为n − m n - mn−m。每次操作最多能让一个重复数字变成某个新值与当前所有元素均不同从而减少一个重复实例。因此操作次数至少为n − m n - mn−m。可达性由于数字值域无上限总可以合理安排操作顺序让每次合并产生的新值不与当前任何元素重复。例如优先合并重复元素或将重复元素与一个足够大的不同元素合并生成唯一的新值。因此最优操作次数就是n − m n - mn−m即所有数字出现次数c n t cntcnt中累加( c n t − 1 ) (cnt - 1)(cnt−1)。2. 算法实现使用哈希表unordered_map统计每个数字出现的次数。遍历哈希表对于出现次数c n t 1 cnt 1cnt1的数字将c n t − 1 cnt - 1cnt−1累加到答案。输出答案。3. 复杂度分析时间复杂度O ( n ) O(n)O(n)只需一次遍历统计次数再遍历哈希表求和。空间复杂度O ( n ) O(n)O(n)哈希表存储不同数字及其出现次数。总结问题的关键在于每次操作可以“消耗”一个重复元素并生成一个唯一的新元素从而逐步消除重复。因此最少操作次数等于重复元素的总数即n nn减去不同数字个数。利用哈希表统计频次即可快速求解。代码简要说明读入n nn和所有元素用unordered_mapll,ll mp记录每个值的出现次数。初始化res 0遍历mp对每个cnt大于1 11的条目将cnt - 1累加到res。输出res。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);unordered_mapll,llmp;ll n;cinn;for(ll i0;in;i){ll x;cinx;mp[x];}ll res0;for(auto[key,cnt]:mp)if(cnt1)rescnt-1;coutres\n;return0;}