自动搬运

查看原文

来自洛谷，原作者为

	Mophie 祈祷着你今后的人生，永远都会有幸福的魔法相伴。

搬运于2025-08-24 22:21:35，当前版本为作者最后更新于2020-05-05 00:51:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先这道题真的很毒瘤，很毒瘤……我在考试时WA了33次（悲壮啊）

这道题需要考虑的细节挺多，我认为是一道绿题到蓝题的难度吧。

接下来，就来看看我的心路历程吧。。。（下面题解用词不当请见谅）

$$Start$$

Part1:看到这道题时的想法

这道题问的是总花费最大和第二大（我一开始看到k大有点慌……结果k<=2)

那奔着从简单到难的想法，先开始考虑最大值。

首先，抓住一个关键词：2|m

这说明我只能够取偶数条路

那现在，就拿m=6举个栗子：

设端点为1~6，则我们可以得到：

所有距离=（1，2）+（1，3）+（1，4）+（1，5）+（1，6）+（2，3）+（2，4）+（2，5）+（2，6）+（3，4）+（3，5）+（3，6）+（4，5）+（4，6）+（5，6）=（（1，2）+（2，6））+（（1，3）+（3，6））+（（1，4）+（4，6））+（（1，5）+（5，6））+（1，6）+（（2，3）+（3，5））+（（2，4）+（4，5））+（2，5）+（3，4）=5（1，6）+3（2，5）+（3，4）

然后我们会吃惊的发现，竟然系数是等差数列！还是奇数等差数列!

这适不适用于所有情况呢？

其实这十分好想，比如说有（1，6),我就要一边的端点是1，一边的端点6，而刚好端点不同可以一一配对，而且也恰好将每条含有1或6的边全部用完，都可以配成$m-1$个对，所以不需再考虑1，6，只需考虑2，3，4，5，以此类推。

所以我们得到了这个看起来很漂亮的式子。既然得到了这个柿子，那有什么用呢？

其实得到了这个柿子，$k=1$就已经做完了。

为什么呢？

其实十分简单。你思考一下，就会很轻松的发现：

肯定从两端开始选喽

因为选两端的话，可以（1，m）,（2，m-1）……都取到最大值

这还是十分明显的。

成功拿到42分！

很好，目前为止一切顺利

（来吧，给自己鼓鼓掌吧）

Part2.推第二大

毒瘤开始

前面我相信大部分人都打出来了

但关键问题在于——第二大肿么推？

其实很简单——把最靠中间的往中间移一格即可。

那问题来了——Why？

首先，动他们两边的就必须要动最中间的。

那最中间的至少要往中间移一格，那么中间的和这个方案一样，两边的减小了，所以成立。

那么-1呢？

他说了没有可能，那么就是当k=2时且m=n嘛。

你自信的交了上去，看见一只只绿鸟亮起十分激动。

结果冒出了零星的几点红色——42

捆绑测试最烦了

你脑子里可能会闪过的一个想法——是不是数据有点问题？

我一开始也是这么想的，但看已经有5个大佬AC，就知道没问题。

我再度审视自己的证明过程，后来举了几个例子后就知道了。

Wrong 1:谁告诉你只有m=n，k=2时才是-1？

我仔细的再看了这个题面，把视线聚焦在了两个字：

严格

第二大，严格，我仿佛知道了什么：要是全是第一大，会怎样？

那怎么才会做到呢？

全部相等不就好了？

所以这个地方需要特判，特判这个情况。

你一边骂骂咧咧的说数据恶心，出这么多-1，一边又交了上去——

哎，几只红鸟变绿了，但依然是42……

我今天就跟42过不去了……

加油吧，继续努力……

Wrong 2:貌似$k=2$的过程有点毛病……

再认认真真的看来一遍我的证明。

突然想到了什么——

万一我两个选的数一样肿么办？

举了个例子发现——那就继续往前选呗

哎，对哎，于是我立马付出了行动。

1分钟敲好了代码

满怀期待的看着评测结果

结果Subtesk1&2全过，你在想：哎，总算过了……

结果……

58……

至少也说的过去了嘛……

是，吗……

满怀绝望也要加油啊！

Wrong 3:Wrong 2的延伸

结果你突然灵机一动，想到一个奇怪的数据：

8 6 2

5 6 6 6 6 6 7 8

结果发现最终的答案是错误的。

Wrong answer:9

correct answer:5（自行手推）

然后你才发现——万一到对面时依然相同，那我这个数又不能换到对面去。

那肿么办呢？

只要把从中间往外延伸第一个跳出这个的，然后变为和那个数相同的不就好了？

比如说，在这个样例中就是把7换成6或者5换成6就好了。

公式自己推问题应该不大，下面注释里也写了。

那接下来看代码，好好理解一下这道好题吧。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
inline long long read()
{
	long long sum=0,naga=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')naga=-1;ch=getchar();}
	while(ch<='9'&&ch>='0')sum=sum*10+ch-'0',ch=getchar();
	return sum*naga;
}//快读 
long long n,m,k,taxi,a[300009];
int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);//排序后从两端收缩 
	if((m==n||a[1]==a[n])&&k==2)
	{
		cout<<-1<<endl;
		return 0;
	}
	long long now=1,cnt=m-1,ans=0;//now记录到第几个点，cnt记录要乘的数，ans统计答案 
	while(cnt>0)//乘积大于零就不断加上去 
	{
		ans+=(a[n-now+1]-a[now])*cnt;
		cnt-=2,now++;
	}
	long long l=m/2,r=n-m/2+1;
	if(k==1)cout<<ans<<endl;//最大值 
	else
	{
		long long r1=r,l1=l,L=0,R=0;
		while(a[r1]==a[r]&&r1>1)r1--;//找最靠左的与右边相同的 
		while(a[l1]==a[l]&&l1<n)l1++;//同上 
		if(r1<=l)L=(2*(l-r1)+1)*(a[l]-a[r1]);//减去失去了的差值和他会做的贡献 
		else L=a[l1]-a[l];//否则就当是中间的直接减掉 
		if(l1>=r)R=(2*(l1-r)+1)*(a[l1]-a[r]); 
		else R=a[r]-a[r1];//同上 
		ans=max(ans-L,ans-R);//最大是ans,那么第二大就是两种方法的最大值 
		cout<<ans<<endl;
	}
	return 0;//完美，收工 
}

最后，再小声BB一句：

我好像是跑的最快的哎（应该是加了快读的缘故……）