admin 管理员组

文章数量: 887007

sicily9162. RAZLIKA

 

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;
}


 



 

转载于:.html

本文标签： sicily9162 RAZLIKA

版权声明：本文标题：sicily9162. RAZLIKA 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732354857h1534141.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。