企业官网建设流程全解析

强迫症

时间限制：1 秒
空间限制：256 MB
知识点：枚举、贪心

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

铁子最近犯上了强迫症，他总是想要把一个序列里的元素变得两两不同，而他每次可以执行一个这样的操作，他可以选择序列里的任意两个元素相加，不妨记作a aa和b bb，然后把a + b a + ba+b放进序列里，再删掉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. 算法实现

1. 使用哈希表unordered_map统计每个数字出现的次数。
2. 遍历哈希表，对于出现次数c n t > 1 cnt > 1cnt>1的数字，将c n t − 1 cnt - 1cnt−1累加到答案。
3. 输出答案。

3. 复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，只需一次遍历统计次数，再遍历哈希表求和。
• 空间复杂度：O ( n ) O(n)O(n)，哈希表存储不同数字及其出现次数。

总结

问题的关键在于每次操作可以“消耗”一个重复元素并生成一个唯一的新元素，从而逐步消除重复。因此最少操作次数等于重复元素的总数，即n nn减去不同数字个数。利用哈希表统计频次即可快速求解。

代码简要说明

• 读入n nn和所有元素，用unordered_map<ll,ll> mp记录每个值的出现次数。
• 初始化res = 0，遍历mp，对每个cnt大于1 11的条目，将cnt - 1累加到res。
• 输出res。

代码内容

#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;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);unordered_map<ll,ll>mp;ll n;cin>>n;for(ll i=0;i<n;i++){ll x;cin>>x;mp[x]++;}ll res=0;for(auto[key,cnt]:mp)if(cnt>1)res+=cnt-1;cout<<res<<'\n';return0;}