题解 P6524 【「Wdoi-1」托卡马克】
首先这道题真的很毒瘤，很毒瘤……我在考试时WA了33次（悲壮啊）
这道题需要考虑的细节挺多，我认为是一道绿题到蓝题的难度吧。
接下来，就来看看我的心路历程吧。。。（下面题解用词不当请见谅）
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的边全部用完，都可以配成
所以我们得到了这个看起来很漂亮的式子。既然得到了这个柿子，那有什么用呢？
其实得到了这个柿子，
为什么呢？
其实十分简单。你思考一下，就会很轻松的发现：
肯定从两端开始选喽
因为选两端的话，可以（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一句：
我好像是跑的最快的哎（应该是加了快读的缘故……）