解释思路

由于袜子丢了且颜色 严格单调递增 ，证明丢失的袜子没有成一对的，则我们可以将读入的丢失袜子的颜色转化为落单的袜子的颜色。而我们只需要处理落单的袜子，因为只有落单袜子对答案有贡献。

分为两种情况：

1. 当落单袜子数量是偶数时，即$K$ % $2$ $==$ $0$时 , 那么很好处理。因为题目给出的颜色为严格单调递增的 ，则相邻两只袜子的颜色值最接近 ，所以算出相邻两个的差的总和即为答案。
2. 当落单的袜子数量时奇数时如果直接逐个枚举，时间复杂度为 $O ( K^2 )$ ，显然会超时；但如果我们预先将前缀和求出来，求值部分时间复杂度就可降低到 $O ( K )$ 。使前缀和数组为 $b$ ，后缀和数组为 $e$ , 则如果要删除第 $i$ 个颜色，当 $i$ 为偶数时，差异和为 $b_{i - 2} + e_{i + 2} + ( a_{i + 1} - a_{i - 1} )$ ；i 为奇数时，差异和为 $b_{i - 1} + e_{i + 1}$ 。很好解释：

• 当 $i$ % $2 == 0$ 时 ， 那么总答案为前面 $i-2$ 个数的答案 （ $i-2$也为偶数，将问题转化为情况1 ） 、后面 $i+2$ 个数的答案 （ 同理 ） 与 $a_{i}-a_{i-1}$ （ 因为删除 $i$ 后旁边两个相邻了 ） 的总和。
• 当 $i$ % $2 == 1$ 时 ， 那么总答案为为前面 $i-1$ 个数的答案 （ $i-1$为偶数，将问题转化为情况1 ） 、后面 $i+1$ 个数的答案 （ 同理 ） 的总和。

代码

照着思路打就行了。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, a[N], ans;
int b[N], e[N];
int main() {
	scanf("%d%d",&n,&k);
	for (int i=1;i<=k;i++)scanf("%d",&a[i]);
	if (k % 2 == 0){//k为偶数
		for(int i=1;i<=k;i+=2)
			ans+=a[i+1]-a[i];
	}else {//k为奇数
		ans=INT_MAX;
		for (int i=2;i<=k;i+=2)//前缀和b
		    b[i]=b[i-2]+a[i]-a[i-1];
		for (int i=k-1;i>0;i-=2)//前缀和e
		    e[i]=e[i+2]+a[i+1]-a[i];
		for (int i=1;i<=k;i+=2)//尝试删除奇数位数
		    ans=min(ans,b[i-1]+e[i+1]);
		for (int i=2;i<=k;i+=2)//尝试删除偶数位数
		    ans=min(ans,b[i-2]+e[i+2]+a[i+1]-a[i-1]);
	}
	printf("%d",ans);
}

注意分类，没分类56(最高60别问我是怎么知道的)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,a[200005],zs[200005],ds[200005],ans;
int main()
{
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=k;i++)scanf("%lld",&a[i]);
	if(k%2==0) //偶数好算,直接两两配对来算 
	{
		ans=0;
		for(int i=1;i<=k;i+=2)ans+=a[i+1]-a[i];
	}
	else//奇数再算哪一个不配对能使值最小 
	{
		for(int i=2;i<=k;i+=2)zs[i]=zs[i-2]+a[i]-a[i-1];//前面 
		for(int i=k-1;i>=1;i--)ds[i]=ds[i+2]-a[i]+a[i+1];//后面 
		ans=0x3f3f3f3f3f3f3f3fll;//求最小,就先最大 
		for(int i=1;i<=k;i+=2)ans=min(ans,zs[i-1]+ds[i+1]);//算出值 
	}
	printf("%lld\n",ans);
	return 0;
}