C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 588K, 提交时间: 2020-05-21 19:21:56

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10,mod=1e9+7; 
int n,m,p,T,res;
int pos[maxn];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&p);
		int index=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&pos[i]);
			if(p>pos[i])	index=i;	
		}
		ll ans=1e17;
		for(int i=1;i<n;i++)
		{
			if(i<index)
			{
				if(m<(index-i+1))	continue;
				ll cnt=m-(index-i+1),res=p-pos[i];
				ans=min(ans,res+cnt*(pos[i+1]-pos[i]));
				if(index<n&&cnt)	ans=min(ans,(cnt-1)*(pos[i+1]-pos[i])+res+2*(pos[index+1]-p));
			}
			else
			{
				if(m<(i-index))	continue;
				ll cnt=m-(i-index),res=pos[i]-p;
				ans=min(ans,res+cnt*(pos[i+1]-pos[i]));
				if(index>0&&cnt)	ans=min(ans,(cnt-1)*(pos[i+1]-pos[i])+res+2*(p-pos[index]));
			}
		}
		printf("%lld\n",ans);
	 } 
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 384K, 提交时间: 2018-01-06 15:34:12

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
int t,n,m,p,k;
const int N =1e5+5;
int a[N];
long long ans;

void work(int k,int w)
{
	for (int i=k;i<=n;i++) if (i>1&&m-(i-k)>=0) ans=min(ans,(ll)w+a[i]-a[k]+((ll)a[i]-a[i-1])*(m-(i-k)));
    for (int i=k-1;i;i--) if (i<n&&m-(k-i)>=0) ans=min(ans,(ll)w+a[k]-a[i]+((ll)(a[i+1]-a[i]))*(m-(k-i)));
}

int main()
{
	cin>>t;
	while(t--)
	{
		ans = 1e18;
		cin>>n>>m>>p;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(k=0;a[k]<p&&k<=n;k++);
		m--;
		if (k<=n)  work(k,a[k]-p);
		if(k>1)    work(k-1,p-a[k-1]);
		cout<<ans<<endl;
    }





	return 0;
}

pypy3 解法, 执行用时: 70ms, 内存消耗: 23160K, 提交时间: 2021-06-03 22:19:29

T = int(input())
for _ in range(T):
	n, m, p = map(int, input().split())
	a = list(map(int, input().split()))
	x = -1
	for i, c in enumerate(a):
		if p > c: x = i
	ans = 1e18
	for i in range(n - 1):
		if i <= x:
			if m < x - i + 1: continue
			d, c = p - a[i], m - (x - i + 1)
			ans = min(ans, d + c * (a[i + 1] - a[i]))
			if c > 0 and x + 1 < n:
				ans = min(ans, (a[x + 1] - p) * 2 + d + (c - 1) * (a[i + 1] - a[i]))
		else:
			if m < i - x: continue
			d, c = a[i] - p, m - (i - x)
			ans = min(ans, d + c * (a[i + 1] - a[i]))
			if c > 0 and x >= 0:
				ans = min(ans, (p - a[x]) * 2 + d + (c - 1) * (a[i + 1] - a[i]))
	print(ans)