整数序列修改代价最小化 - 算法解析及C++代码实现

"整数序列修改代价最小化 - 算法解析及C++代码实现"\n\n给定整数序列 \na, 你要对每一个\na\ni\n 进行恰好一次修改操作, 使得 \na 中每个元素都相等, 且都为整数.\n\n把 \nx 变成 \ny 花费的代价是 \n(\nx−\ny\n)2\n(x−y)2\n , 求最小代价.\n\n注意, 可以把 \nx 变成 \nx .\n\n数据格式\n输入格式\n第一行一个整数 \nn, 表示序列长度.\n\n接下来一行 \nn 个整数, 表示序列 \na.\n\n输出格式\n输出一行一个整数, 表示最小代价.\n\n测试样例\n输入数据 1\n5\n5 -2 5 -1 -2\n输出数据 1\n54\n输入数据 2\n8\n8 6 5 -8 -1 -1 -8 5\n输出数据 2\n276\n数据范围\n1\n≤\nn\n≤\n3000\n1≤n≤3000\n\n−\n1000\n≤\na\ni\n≤\n1000\n−1000≤a\ni\n ≤1000\n\n用C++做出这道题内容：算法思路：\n1. 先找到序列中出现次数最多的数，将它作为目标数。\n2. 遍历序列，将每个数与目标数的差的平方累加得到总代价。\n\n具体实现：\n1. 使用unordered_map统计序列中每个数的出现次数。\n2. 遍历unordered_map，找到出现次数最多的数，作为目标数。\n3. 遍历序列，计算每个数与目标数的差的平方累加得到总代价。\n4. 输出总代价。\n\nC++代码实现如下：\n\ncpp\n#include <iostream>\n#include <unordered_map>\n#include <cmath>\nusing namespace std;\n\nint main() {\n int n;\n cin >> n;\n \n unordered_map<int, int> count;\n int maxCount = 0;\n int target = 0;\n \n for (int i = 0; i < n; i++) {\n int num;\n cin >> num;\n count[num]++;\n if (count[num] > maxCount) {\n maxCount = count[num];\n target = num;\n }\n }\n \n int cost = 0;\n for (auto it = count.begin(); it != count.end(); it++) {\n int num = it->first;\n cost += pow(num - target, 2) * it->second;\n }\n \n cout << cost << endl;\n \n return 0;\n}\n\n\n时间复杂度分析：\n遍历序列和unordered_map的时间复杂度均为O(n)，总时间复杂度为O(n)。\n\n