= =本来昨天就该发的，只是断网……。
MATH
【题目描述】
小 x正在做他的数学作业，可是作业实在太难了。题目是这样的：
1.给定一个含有N个数的数列 V。
2.你可以从数列中恰好移除 K个数,定义移除后的数列为 V’。
3.定义M为V’中任意两个数的差的最大值，m为 V’中任意两个数的差的最小值。
4.请你选择删去的K 个数，使得M+m最小。
小 x的数学十分之差，于是他只能向你求助了。
【输入】
第一行两个整数 N和K。
第二行N个整数Vi。
【输出】
一行一个整数，为最小的M+m的和。
【样例输入】
5 2
-3 -2 3 8 6
【样例输出】
7
【样例解释】
删去-3 和-2，得到 V’={3,6,8}，M=5,m=2,M+m=7。
【数据范围】
对于60%的数据：3 ≤ N ≤ 2 000
对于100%的数据：
3 ≤ N ≤ 200 000
1 ≤ K ≤ N - 2
-5 000 000 ≤Vi ≤ 5 000 000
对于这道题，乍一看很绕……实际也很绕，但是做法很简单。
首先，我们对原序列排序，排了序之后，枚举长度为（n-k）的区间求最大差和最小差的差（= =），然后打擂求出最小即可。
因为我们可以证明，删去元素后得到的最优序列排了序之后一定是连续的，所以只需要枚举就可以了。（证明略）
但是最后求区间最小差的时候要用倍增ST算法，不然会超时……
代码如下（风格丑别在意）
1 #include <algorithm> 2 #include <iostream> 3 #include <fstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <string> 7 #include <cmath> 8 using namespace std; 9 ifstream fin("math.in"); 10 ofstream fout("math.out"); 11 long long int Beiz[200005][25][2]={0};//ｱｶﾔ・ 12 long long int xl[200005]={0};//ﾐ�ﾐ 13 long long int ca[200005]={0};//iｺﾍi+1ｵﾄｲ・ 14 int C2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288}; 15 long long int num=0,cut=0; 16 bool px(long long int a,long long int b); 17 void beiz(int cs); 18 long long int findi(long long int begin,long long int end); 19 int main(void) 20 { 21 fin>>num>>cut; 22 for(int i=1;i<=num;i++)fin>>xl[i]; 23 sort(xl+1,xl+num+1,px); 24 for(int i=1;i<=num;i++) 25 { 26 ca[i]=abs(xl[i+1]-xl[i]); 27 Beiz[i][0][0]=ca[i]; 28 Beiz[i][0][1]=i+1; 29 } 30 beiz(1); 31 long long int rest=num-cut-1; 32 long long int ans=0x7fffffffffffffffll,tot=0; 33 for(int i=1;i<=cut+1;i++) 34 { 35 if(i+rest>num)break; 36 tot=abs(xl[i+rest]-xl[i])+findi(i,i+rest-1); 37 ans=min(tot,ans); 38 } 39 fout<<ans; 40 return 0; 41 } 42 43 bool px(long long int a,long long int b) 44 { 45 if(a<b)return 1; 46 return 0; 47 } 48 49 void beiz(int cs) 50 { 51 if(cs==20)return; 52 for(int i=1;i<=num;i++) 53 { 54 Beiz[i][cs][1]=Beiz[Beiz[i][cs-1][1]][cs-1][1]; 55 Beiz[i][cs][0]=min(Beiz[Beiz[i][cs-1][1]][cs-1][0],Beiz[i][cs-1][0]); 56 } 57 beiz(cs+1); 58 } 59 60 long long int findi(long long int begin,long long int end) 61 { 62 long long int L1=0,L2=0,Mid=0; 63 double K=log((double)(end-begin))/log((double)2); 64 Mid=(int)K; 65 L1=Beiz[begin][Mid][0]; 66 L2=Beiz[end-C2[Mid]+1][Mid][0]; 67 return min(L1,L2); 68 }