企业官网建设流程全解析

一、题目描述1. 题干小明的老师准备组织一次班级活动。班上一共有 n 名n 为偶数同学老师想把所有的同学进行分组每两名同学一组。为了公平老师给每名同学随机分配了一个 n 以内的正整数作为 id第 i 名同学的 id 为 ai​。老师希望通过更改若干名同学的 id 使得对于任意一名同学 i有且仅有另一名同学 j 的 id 与其相同ai​aj​。请问老师最少需要更改多少名同学的 id2. 输入输出示例输入示例输出示例说明41 2 2 31仅需要把 a1​ 改为 3 或者把 a4​ 改为 1 即可。3. 约束条件对于 20% 的数据保证 n≤10^3。对于 100% 的数据保证 n≤10^5。二、思路1. 核心逻辑推导要实现每个ID恰好出现2次配对的目标无需复杂操作只需先明确两类需要处理的ID场景再针对性计算修改次数多余次数的ID若某个ID出现次数 2超出2次的部分必须修改例如出现3次需修改1次出现4次需修改2次单次出现的ID若某个ID仅出现1次每2个这样的ID可配对修改修改其中1个即可组成一对例如2个单次ID需修改1次3个单次ID需修改1次。2. 贪心策略设计基于上述分析设计两个核心统计变量用于计算最少修改次数c1出现次数为1的ID数量c2出现次数 2的ID的多余次数总和(ID出现总次数 - 2。结合贪心思想最终修改次数的计算规则如下若c2c1多余次数可完全覆盖单次ID的配对需求最少修改次数为c2若c1c2先消耗 c2 覆盖部分单次ID剩余单次ID每2个修改1次最终次数为c2 (c1 - c2) / 2。三、算法执行流程读取输入数据初始化哈希表用于统计ID出现频次和数组用于存储ID遍历ID数组完成所有ID的频次统计存入哈希表 (若题目明确ID的取值范围可使用数组替代哈希表进一步降低空间开销提升访问效率)遍历哈希表分别统计 c1单次ID数和 c2多余次数总和根据 c1 和 c2 的大小关系计算并输出最少修改次数。四、完整代码实现Javaimport java.util.*; public class Main{ public static void main(String[] args){ Scanner scnew Scanner(System.in); int nsc.nextInt(); int[] arrnew int[n]; MapInteger,Integer mapnew HashMap(); for(int i0;in;i){ arr[i]sc.nextInt(); //getOrDefault不存在则默认0存在则取当前值1 map.put(arr[i],map.getOrDefault(arr[i],0)1); } int ans0; int c10; int c20; //遍历哈希表的键值对 for(Map.EntryInteger,Integer x: map.entrySet()){ if(x.getValue()2){ c2x.getValue()-2; }else if(x.getValue()1){ c11; } } if(c2c1){ System.out.println(c2); }else if(c1c2){ System.out.println(c2(c1-c2)/2); } } }五、总结本题的核心是“哈希表频次统计 贪心策略”整体思路简洁、高效重点掌握以下两点哈希表的高效使用解决“无序数据的频次统计”问题避免空指针异常提升统计效率贪心思想的应用通过分类统计“多余次数”和“单次ID数”找到最少修改次数的最优解无需复杂计算。如果大家有更优的思路或者发现文中的纰漏欢迎大家在评论区交流讨论