9162. RAZLIKA
限制条件
时间限制: 2 秒, 内存限制: 256 兆
题目描述
Mirko's newest math homework assignment is a very difficult one! Given a sequence, V, of N integers,
remove exactly K of them from the sequence. Let M be the largest difference of any two remaining
numbers in the sequence, and m the smallest such difference. Select the K integers to be removed from
V in such a way that the sum M + m is the smallest possible. Mirko isn't very good at math, so he has
asked you to help him!
输入格式
The first line of input contains two positive integers, N (3 ≤ N ≤ 1 000 000) and K (1 ≤ K ≤ N - 2).
The second line of input contains N space-separated positive integers – the sequence V (-5 000 000 ≤
Vi ≤ 5 000 000).
输出格式
The first and only line of output must contain the smallest possible sum M + m.
样例输入
5 2
-3 -2 3 8 6
样例输出
7
题目来源
2013年每周一赛第10场/COCI 2013.1
题意：给你一串数字，叫你先删除k个然后再找出剩下的点中最长距离和最小距离和最小
看一下题的数据量3 ≤ N ≤ 1 000 000，吓死人，这些数据要在2s内完成，绝对不能两层循环以上
刚开始还没什么想法，后来隔了几天在想一下。先排好序。然后删除的时候绝对不能使从中间的数删除的
只有从两边删除。因为如果是从中间删除我一定可以找到从两边删除会比他更优。所以就从头到尾循环
每次更新最长和最短距离之和就ok了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int array[1000006];
int p[1000006];
int Min(int a,int b)
{
return a>b?b:a;
}
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
for(int i=0;i<n;i++)
scanf("%d",&array[i]); sort(array,array+n);
for(int i=0;i<n-1;i++)
p[i] = array[i+1]-array[i];
int c = n-k;
int l;
int last = -1;
int min = 20000002;
for(int j=0;j<k;j++)
{
l = array[c+j-1] - array[j];
if(last>=j && last<c+j-1)
{
if(p[last]>=p[c+j-2])
last = c+j-2;
}
else
{
int var = 20000001;
for(int k=j;k<c+j-1;k++)
if(p[k]<=var)
{
last = k;
var = p[k];
}
}
min = Min(min,l+p[last]);
} printf("%d\n",min);
}
return 0;
}