sjtu1333 函数时代

Description

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

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

给定\(n\)个数,第\(i\)个数为\(a[i]\)。再给定一个常数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 \le 1000\)。

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

这题写了个奇怪的算法。我想肯定有某种分法使得最优解涵盖在里面。

我是这样做的。将\(a\)排序。开始时把所有元素都放入一个集合中,然后把依次\(a[i]\)放入另一个集合中,边放边维护答案就可以了。

如何证明脑补一下就行了吧(大概是让最小值变大)。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std; #define maxn (100010)
int N,H,A[maxn],ans; int main()
{
freopen("1333.in","r",stdin);
freopen("1333.out","w",stdout);
scanf("%d%d",&N,&H);
for (int i = 1;i <= N;++i) scanf("%d",A+i);
sort(A+1,A+N+1);
ans = A[N]+A[N-1]-A[1]-A[2];
for (int i = 1;i <= N-2;i += 2)
{
int mi = min(A[1]+A[2]+H,A[i+1]+A[i+2]),ma = max(A[N]+A[N-1],A[N]+A[1]+H);
if (i > 1) ma = max(ma,A[i]+A[i-1]+H),mi = min(mi,A[1]+A[3]);
ans = min(ans,ma-mi);
}
printf("%d",ans);
fclose(stdin); fclose(stdout);
return 0;
}
上一篇:Codeforces 15B Laser


下一篇:Android4.0+锁屏程序开发——设置锁屏页面篇