算法
(贪心) $O(n)$
原题其实就是问去掉下面哪条边可使得总距离最短。
显然我们只需要去掉长度最长的那条边 $l$ 即可,而答案就是 $k - l$。
这里为了处理方便,我们可以破环成链。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
int main() {
int k, n;
cin >> k >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
a.push_back(a[0] + k);
int l = 0;
rep(i, n) {
l = max(l, a[i + 1] - a[i]);
}
int ans = k - l;
cout << ans << '\n';
return 0;
}