企业官网建设流程全解析

免费个人网站注册方法,免费的网站推广方法,好点的开发网站的公司,网站建设集团P14917 [GESP202512 五级] 数字移动 题目描述 小 A 有一个包含 NNN 个正整数的序列 A{A1,A2,⋯ ,AN}A\{A_1,A_2,\cdots,A_N\}A{A1​,A2​,⋯,AN​}#xff0c;序列 AAA 恰好包含 N2\frac{N}{2}2N​ 对不同的正整数。形式化地#xff0c;对于任意 1≤i≤N1 \le i \le N1≤i≤…P14917 [GESP202512 五级] 数字移动题目描述小 A 有一个包含NNN个正整数的序列A{A1,A2,⋯ ,AN}A\{A_1,A_2,\cdots,A_N\}A{A1​,A2​,⋯,AN​}序列AAA恰好包含N2\frac{N}{2}2N​对不同的正整数。形式化地对于任意1≤i≤N1 \le i \le N1≤i≤N存在唯一一个jjj满足1≤j≤N,i≠j,AiAj1\le j \le N, i\neq j, A_iA_j1≤j≤N,ij,Ai​Aj​。小 A 希望每对相同的数字在序列中相邻为了实现这一目的小 A 每次操作会选择任意i(1≤i≤N)i(1\le i\le N)i(1≤i≤N)将当前序列的第iii个数字移动到任意位置并花费对应数字的体力。例如假设序列A{1,2,1,3,2,3}A\{1,2,1,3,2,3\}A{1,2,1,3,2,3}小 A 可以选择i2i2i2将A22A_22A2​2移动到A31A_31A3​1的后面此时序列变为{1,1,2,3,2,3}\{1,1,2,3,2,3\}{1,1,2,3,2,3}耗费222点体力。小 A 也可以选择i3i3i3将A31A_31A3​1移动到A22A_22A2​2的前面此时序列变为{1,1,2,3,2,3}\{1,1,2,3,2,3\}{1,1,2,3,2,3}花费111点体力。小 A 可以执行任意次操作但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的xxx使得他能够在每次花费的体力均不超过xxx的情况下令每对相同的数字在序列中相邻。输入格式第一行一个正整数NNN代表序列长度保证NNN为偶数。第二行包含NNN个正整数A1,A2,…,ANA_1,A_2,\ldots,A_NA1​,A2​,…,AN​代表序列AAA。且对于任意1≤i≤N1\le i\le N1≤i≤N存在唯一一个jjj满足1≤j≤N,i≠j,AiAj1\le j\le N,i\neq j,A_iA_j1≤j≤N,ij,Ai​Aj​。数据保证小 A 至少需要执行一次操作。输出格式输出一行代表满足要求的xxx的最小值。输入输出样例 #1输入 #16 1 2 1 3 2 3输出 #12说明/提示对于40%40\%40%的测试点保证1≤N,Ai≤1001\le N,A_i\le 1001≤N,Ai​≤100。对于所有测试点保证1≤N,Ai≤1051\le N,A_i\le 10^51≤N,Ai​≤105。题解P14917 数字移动一、题目核心分析1. 题目本质给定一个长度为偶数NNN的序列序列中恰好包含N2\frac{N}{2}2N​对不同的正整数每个数字恰好出现两次。我们需要找到最小的xxx使得每次操作花费移动数字的大小均不超过xxx时能让每对相同数字相邻。每次操作可将任意位置的数字移动到任意位置花费为该数字的大小。2. 解题核心思路本题采用二分查找结合合法性校验的策略二分查找的范围左边界left0left0left0右边界rightrightright为序列中的最大数字因为最坏情况下需要移动最大的数字。合法性校验对于给定的候选值xxx判断是否能在每次操作花费不超过xxx的前提下实现所有相同数字相邻。// 引入万能头文件包含C所有常用标准库如iostream、algorithm等无需单独引入#includebits/stdc.h// 使用std命名空间避免每次调用库函数都写std::如std::cin → cinusingnamespacestd;constintMAXN1e55;// 定义数组最大长度1e5对应题目中N≤10^5的限制5防止越界intn;// 序列长度全局变量方便check函数直接访问inta[MAXN];// 存储输入的序列/** * brief 合法性校验函数判断候选值x是否满足要求每次操作花费≤x时能让所有相同数字相邻 * param x 候选的最大允许花费 * return bool true表示x合法false表示不合法 */boolcheck(intx){intcnt0;// 统计序列中x的数字个数这些数字无法移动只能留在原位置intpre0;// 记录第奇数个x的数字用于匹配第偶数个x的数字// 遍历整个序列检查无法移动的数字是否能天然两两配对for(inti1;in;i){// 若当前数字x说明移动它的花费超过x无法移动必须留在原位置if(a[i]x){cnt;// 无法移动的数字计数1// 奇数个无法移动的数字记录下来等待后续配对if(cnt%21){prea[i];}// 偶数个无法移动的数字必须和前一个pre相同否则无法配对相邻else{if(a[i]!pre){returnfalse;// 配对失败x不合法}}}}// 所有无法移动的数字都成功两两配对x合法returntrue;}intmain(){// 步骤1输入处理 初始化二分查找边界cinn;// 读取序列长度nintleft0;// 二分左边界最小可能的花费初始为0intright0;// 二分右边界最大可能的花费初始为0后续更新为序列最大值for(inti1;in;i){cina[i];// 读取序列的第i个元素rightmax(right,a[i]);// 更新右边界为序列中的最大值最坏情况需要移动最大数字}// 步骤2二分查找最小合法x二分模板寻找最小满足条件的值// 循环条件right left 1 → 确保最终收敛到最小合法值while(rightleft1){intmid(leftright)/2;// 计算中间值候选xif(check(mid)){// 若mid合法能通过校验rightmid;// 尝试找更小的合法值将右边界收缩到mid}else{// 若mid不合法leftmid;// 需要增大候选值将左边界扩展到mid}}// 步骤3输出结果循环结束后right即为最小合法x// 原因二分过程中right始终保持为合法值left始终为不合法值最终收敛到最小合法值coutrightendl;return0;// 程序正常结束}二、代码逻辑核心解读1. 合法性校验函数核心逻辑这是本题的核心函数用于判断候选值xxx是否合法变量定义cntcntcnt统计序列中大于xxx的数字的个数这些数字无法被移动因为移动它们的花费会超过xxx只能保留在原位置。preprepre记录第奇数个大于xxx的数字用于匹配第偶数个大于xxx的数字。遍历序列的核心逻辑当遇到大于xxx的数字时该数字无法移动计数器cntcntcnt加 1。若cntcntcnt是奇数当前是第1、3、5…个大于xxx的数字将该数字存入preprepre等待后续匹配。若cntcntcnt是偶数当前是第2、4、6…个大于xxx的数字必须与前一个preprepre存储的大于xxx的数字相同若不相同说明这两个无法移动的数字无法配对相邻xxx不合法。若相同说明这对数字可以自然配对继续遍历。遍历结束后所有大于xxx的数字都成功两两配对说明xxx合法。关键逻辑解读大于xxx的数字无法移动因此它们必须在原序列中天然地两两出现奇偶位置对应配对否则无法实现相邻而小于等于xxx的数字可以自由移动花费不超过xxx总能调整位置实现两两相邻。2. 主函数核心逻辑输入处理读取序列长度nnn和序列数组初始化二分查找的左右边界左边界left0left0left0右边界rightrightright为序列中的最大数字。二分查找循环循环条件rightleft1采用闭区间二分的优化写法确保最终收敛到最小的合法xxx。计算中间值mid(leftright)/2mid(leftright)/2mid(leftright)/2候选xxx。若候选值合法说明midmidmid是合法值尝试寻找更小的合法值将右边界rightrightright更新为midmidmid。若候选值不合法说明midmidmid不合法需要增大候选值将左边界leftleftleft更新为midmidmid。结果输出循环结束后rightrightright即为最小的合法值输出rightrightright核心原因二分查找过程中rightrightright始终保持为合法值leftleftleft始终保持为不合法值最终收敛时rightrightright是最小合法xxx。三、时间复杂度分析二分查找次数最多log⁡2(max(A))\log_2(max(A))log2​(max(A))由于Ai≤105A_i\le10^5Ai​≤105log⁡2(105)≈17\log_2(10^5)\approx17log2​(105)≈17次。每次合法性校验函数时间复杂度O(n)O(n)O(n)遍历一次序列。总时间复杂度O(nlog⁡max(A))O(n\log max(A))O(nlogmax(A))满足n≤105n\le10^5n≤105的数据范围要求运行高效。四、总结本题核心是二分查找最小合法xxx合法性校验的关键是判断“无法移动的数字大于xxx”是否能天然两两配对。二分查找过程中rightrightright始终保留为合法值leftleftleft始终保留为不合法值最终收敛到最小合法值。该解法时间复杂度优秀能满足题目所有数据范围的要求是解决此类“最小最大值”问题的经典模板。