【题目来源】洛谷B4495 [GESP202603 一级] 交朋友 - 洛谷【题目描述】Alice 班上共有 4 个小朋友身高分别为H 1 H_1H1​,H 2 H_2H2​,H 3 H_3H3​,H 4 H_4H4​其中 Alice 的身高为H 1 H_1H1​。Alice 想要和身高最接近她的人交朋友如果有多个人符合条件则 Alice 想和其中较矮的那一人做朋友你能告诉她这个人的身高是多少吗【输入】输入共 4 行第i ii行包含一个整数H i H_iHi​表示班上小朋友的身高。【输出】输出 1 行包含一个整数h hh表示 Alice 想交的朋友的身高。【输入样例】150 165 135 133【输出样例】135【核心思想】问题分析给定 4 个身高值H 1 , H 2 , H 3 , H 4 H_1, H_2, H_3, H_4H1​,H2​,H3​,H4​H 1 H_1H1​为 Alice 的身高需要在H 2 , H 3 , H 4 H_2, H_3, H_4H2​,H3​,H4​中找到与H 1 H_1H1​身高差绝对值最小的人。若存在多人身高差相同则选择身高较矮者。本质是带平局处理的最小距离搜索问题。算法选择线性扫描比较初始化最优候选为H 2 H_2H2​依次与H 3 , H 4 H_3, H_4H3​,H4​比较根据比较规则更新最优解关键步骤初始化最优身高minh H 2 \text{minh} H_2minhH2​最小高度差minn ∣ H 1 − H 2 ∣ \text{minn} |H_1 - H_2|minn∣H1​−H2​∣遍历比较对H 3 , H 4 H_3, H_4H3​,H4​计算当前高度差d ∣ H i − H 1 ∣ d |H_i - H_1|d∣Hi​−H1​∣若d minn d \text{minn}dminn更新minh H i \text{minh} H_iminhHi​minn d \text{minn} dminnd否则若d minn d \text{minn}dminn且H i minh H_i \text{minh}Hi​minh更新minh H i \text{minh} H_iminhHi​平局时选较矮者输出结果minh \text{minh}minh时间/空间复杂度时间复杂度O ( 1 ) O(1)O(1)固定 3 次比较空间复杂度O ( 1 ) O(1)O(1)仅使用常数个变量带平局处理的最小距离搜索核心思想双重比较条件优先比较距离身高差绝对值距离更小时无条件更新距离相等时引入第二关键字身高本身进行平局裁决贪心局部最优每次比较只关注当前候选与当前最优的相对关系由于比较规则具有传递性线性扫描即可得到全局最优初始化策略将第一个候选H 2 H_2H2​作为初始最优解避免空值判断简化代码结构可扩展性虽然本题固定为 4 人但算法可自然扩展到N NN人场景循环遍历H 2 H_2H2​到H N H_NHN​适用于带优先级排序的最近邻搜索、多关键字比较等基础决策问题【算法标签】#入门 #语法基础【代码详解】#includebits/stdc.husingnamespacestd;intmain(){inth1,h2,h3,h4;// 定义四个整数变量表示四个高度cinh1h2h3h4;// 从标准输入读取四个高度值intminhh2;// 初始化最小高度差对应的高度为h2intminnabs(h1-h2);// 初始化最小高度差为h1和h2的差的绝对值// 比较h3和h1的高度差if(abs(h3-h1)minn||(abs(h3-h1)minnh3minh)){minhh3;// 如果h3的高度差更小或者高度差相同但h3更矮则更新最小高度minnabs(h3-h1);// 更新最小高度差}// 比较h4和h1的高度差if(abs(h4-h1)minn||(abs(h4-h1)minnh4minh)){minhh4;// 如果h4的高度差更小或者高度差相同但h4更矮则更新最小高度minnabs(h4-h1);// 更新最小高度差}coutminhendl;// 输出与h1高度差最小的高度值如果高度差相同则输出较小的那个高度return0;// 程序正常结束}【运行结果】150 165 135 133 135