问题 L: 简单的旅行商
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：266
解决：102
题目描述
我们知道,旅行商问题是一个 $\text{NP-Hard}$ 问题,研究的是图中无重复访问点的最短路径。
我们给定一个周长为 $C$ 的圆,在圆上有 $n$ 个节点.
从圆上某一点开始,沿着一个方向行走,在行走距离 $a_i$ 后有一个节点 $i$
你可以沿着圆周,从任意方向行走,这样我们就得到一个环状的无向图。
请你在图中找到一条路径,使得每个节点恰好访问一次,且路径长度最短.
请你输出这个最短路径的长度
我们给定一个周长为 $C$ 的圆,在圆上有 $n$ 个节点.
从圆上某一点开始,沿着一个方向行走,在行走距离 $a_i$ 后有一个节点 $i$
你可以沿着圆周,从任意方向行走,这样我们就得到一个环状的无向图。
请你在图中找到一条路径,使得每个节点恰好访问一次,且路径长度最短.
请你输出这个最短路径的长度
输入
输入第一行,两个整数,$C,n$,分别代表圆的周长以及节点个数.
输入第二行,$n$ 个递增的整数 $a_i$ ,代表每个节点在圆上的相对位置.
$ (2 \leq C \leq 10^6, 2 \leq n \leq 2 \times 10^5)$
$( 0 \leq a_1 < a_2 < ... < a_n < C)$
输入第二行,$n$ 个递增的整数 $a_i$ ,代表每个节点在圆上的相对位置.
$ (2 \leq C \leq 10^6, 2 \leq n \leq 2 \times 10^5)$
$( 0 \leq a_1 < a_2 < ... < a_n < C)$
输出
输出一个整数,代表最短路径长度
样例输入 复制
20 3
5 10 15样例输出 复制
10提示
样例中三点的位置关系如图，最短的路径是 1->2->3 长度为10