20200709 T1 笔记

题目描述

给定一个长度为 (m) 的序列 (a),下标编号为 (1 sim m)。序列的每个元素都是 (1 sim n) 的整数。定义序列的代价为

[largesum_{i=1}^{m-1}|a_{i+1}-a_i| ]

你现在可以选择两个数 (x)(y),并将序列 (a) 中所有的 (x) 改成 (y)(x) 可以与 (y) 相等。

请求出序列最小可能的代价。

输入格式

输入第一行包含两个整数 (n)(m)

第二行包含 (m) 个空格分隔的整数,代表序列 (a)

输出格式

输出一行,包含一个整数,代表序列最小的代价。

样例

1.in

4 6
1 2 3 4 3 2

1.out

3

2.in

10 5
9 4 3 8 8

2.out

6

数据范围与约定

对于(30\%)的数据,(n, m leq 100)

对于(60\%)的数据,(n,m leq 2000)

对于(100\%)的数据,(1 leq n,m leq 100,000)

题解

Code

原文地址:https://www.cnblogs.com/poi-bolg-poi/p/13277373.html