【问题描述】
给定一个长度为m的序列a，下标编号为1~m。序列的每个元素都是1~n的
整数。定义序列的代价为
你现在可以选择两个数x和y，并将序列a中所有的x改成y。x可以与y相等。请求出序列最小可能的代价。
【输入格式】
输入第一行包含两个整数n和m。第二行包含m个空格分隔的整数，代表序
列a。
【输出格式】
输出一行，包含一个整数，代表序列最小的代价。
【样例输入 1】
4 6
1 2 3 4 3 2
【样例输出 1】
3
【样例输入 2】
10 5
9 4 3 8 8
【样例输出 1】
6
【样例解释】
样例 1 中，最优策略为将 4 改成 3。样例 2 中，最优策略为将 9 改成 4。
【数据规模和约定】
对于30%的数据 n, m <=100
60%的数据，n,m≤ 2000。
对于100%的数据，1 ≤ n,m ≤ 100,000。
思路：读入数列， 将相邻的数建一条边。
可以用vector动态二维数组来存一个类似于 邻接链表的东西 （只是类似）。
第一维是 第 i 个数，二维是 第 i 个数相连的数。 注意当i=0 和 i=m 时的情况。
预处理完后 。接下来是操作， 把第 i 个数连接的所有数找出中位数，改变中位数即可达到目的。
因为找中位数需要将 i 连接的整个序列遍历一边。十分麻烦。
所以就可以将 第 i 个数所连接数的数列排一遍序 。中间的数即为 中位数 。
用before 存 原来 第 i 个数所连接数的数列 的价值
after 存 改变后第 i 个数所连接数的数列 的价值，
做before 与 after 的 差即为 要改变的价值 ，把这个价值与上一个价值 取较大值，最终即为要改变的值，
最后 用Sum 存起 所有before 的 和，即为 该序列需求的值。
但是！！ 由于 前后两个数加了两遍
如图，所有的数都被加了两遍 所以答案要 除 2 最后减去 上面求出的要改变的值 即为答案
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring>d #include <algorithm> #include <vector> #define Max 1000001 using namespace std; int N, M; int number [Max]; vector < int > test [Max]; long long Answer, Sum; int max (int a, int b) { return a > b ? a : b; } int abs (int a) { return a < 0 ? -a : a; } int main() { ios :: sync_with_stdio (false); cin >> N >> M; for (int i = 1; i <= M; i++) cin >> number [i]; for (int i = 1; i <= M; i++) { if (i > 1 && number [i - 1] != number [i]) // 防止i等于0 因为下标为0的元素不属于序列 test [number [i - 1]].push_back (number [i]); //建立 类似 于邻接矩阵的东西 ( test [i] 表示 数 i 连接的数有什么) if (i < M && number [i + 1] != number [i]) //防止 超出最大长度 test [number [i + 1]].push_back (number [i]); //同上 } for (int i = 1; i <= N; i++) { if (test [i].size() == 0) //如果第 i 个点没有连接其他点 ，即 没有出现过这个数 ，就跳过 continue; sort (test [i].begin (), test [i].end ()); //把这个数连接 的数 排一遍序 中间的数即为中位数 int y = test [i][test [i].size () >> 1]; //找出中位数 long long before = 0; long long after = 0; for (int j = 0; j < test [i].size (); j++) { before += abs (i - test [i][j]); // 改变之前之前的价值总和 after += abs (y - test [i][j]); // 改变之后的 价值总和 } Answer = max (Answer, before - after); //before - after 是 整个序列改变的值 ，因为要是序列总和尽量小，所以改变的值要尽量大 Sum += before; // Sum 为之前 的 到 第 i 个数的总和 } cout << Sum / 2 - Answer << endl; //因为每个数都加了2遍，所以要除2 后再减去最大的改变值 return 0; }