Skip to content

11333: 【原1333】函数时代

题目

题目描述

author: 李佳骏 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1333

Description

Taring说:生活的过程就是执行函数的过程。需要命令,也需要回报。更重要的,是得到回报的过程。

好吧。。。这道题其实和上面的也没啥关系TAT,我们要求的是下面的问题:

给定n个数,第i个数为Ai。再给定一个常数h。现在,你要把这n个数,分成两个集合,且这两个集合的并集为这n个数的全集;这两个集合的交集为空集。然后我们对于任意的两个数a[i], a[j],做一个函数f(a[i], a[j]) ,此函数满足:

若a[i]和a[j]在同一个集合,那么 f(a[i], a[j]) = a[i] + a[j];

若a[i]和a[j]在不同集合,那么 f(a[i], a[j]) = a[i] + a[j] + h.

现在Taring要使得所有这些函数的最大值和最小值的差最小,请求出这个最小差。

Input Format

第一行有两个数字,n和h。

第二行有n个数字,第i个数据为a[i]。

Output Format

有且只有一个整数,为题目要求所求的最小差。

Sample Input

3 2
1 2 3

Sample Output

1

Constraints

对于30%的数据,n<=1000。

对于100%的数据,n<=100000,h,a[i]<=10^8

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!