时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
查看运行结果
题目描述 Description
小徐从美国回来后,成为了USACO中国区的奶牛销售代理商,专门出售质优价廉的“FJ”牌奶牛。上题中,小徐终于凑够了钱,把她的小伙伴们接过来。
现在,她需要给她自己和其他3个伙伴安排房间。在同一直线上有N间房子(2<=N<=10^5),每间房子有一个唯一的位置(即X坐标)Xi。
(0<=Xi<=10^9)。为了方便交流,请你写一个程序,安排4间房子,使它们的最远距离最短。
输入描述 Input Description
第一行:一个正整数N
第二行:N个正整数,Xi,空格隔开
输出描述 Output Description
最短的最远距离
样例输入 Sample Input
7
1 7 4 20 13 2 11
样例输出 Sample Output
3(选择1、2、4、7)
数据范围及提示 Data Size & Hint
这个。就是二分。
设f(x)为最远距离为x时能否安排4间房子
这个函数当然有单调性,所以,果断二分搜索x。
错误理解:不是寻找坐标最小的,而是寻找x之差最小的
错误代码:
#include
using namespace std;
#include
#include
int p[100100];
int n;
int cmp(const int &a,const int &b)
{
return a>b;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d",&p[i]);
sort(p+1,p+n+1);
int a[3];
for(int i=1,j=0;i<=3;++i,++j)
a[j]=p[i+1]-p[i];
sort(a,a+3,cmp);
printf("%d\n",a[0]);
return 0;
}
正确代码:
方法一:贪心:全搜索法:
#include
using namespace std;
#include
#include
#include
int p[100100];
int n;
int remax(int a,int b)
{
if(a>=b) return a;
return b;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d",&p[i]);
sort(p+1,p+n+1);
int min=pow(10,8);
int t[4];
for(int i=1;i<=n-3;++i)
{
t[1]=p[i+1]-p[i];
t[2]=p[i+2]-p[i+1];
t[3]=p[i+3]-p[i+2];
int fur=remax(remax(t[1],t[2]),t[3]);
if(fur
min=fur;
}
printf("%d\n",min);
return 0;
}