[CF231DPhysical Education and Buns]解题报告

本文主要是介绍[CF231DPhysical Education and Buns]解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题应该有好多好多做法。。每个都差一点想到了，但还是没有想到正解。（最后用了一个二分套二分。。数据大的时候特别容易对，数据小的时候特别容易错；所以WA了第一个点。）
①没有想到枚举公差的时候只与在线最上面的点和在线最下面的点有关，即首项=Max+Min>>1.（！！如果我们注意到与某些量没有关系，那么我们就不要考虑他们好了。）
②算出P∈[0, $\lceil \frac {4*10^6} {n-1} \rceil$ ]之后，没有意识到我们可以在此基础上枚举n，使得时间复杂度为 $4*10^6$ .
③凸包的解法也是很漂亮的，没错在线最上面的点和在线最下面的点确实是在凸包上；这我也没想到。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#include<cmath>
int in(){char c=getchar();int x=0;bool flag=0;for(;c<'0'||c>'9';c=getchar())flag|=c=='-';for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return flag?-x:x;
}
int a[100005],n;
int cal(int x,int p){//计算当首项为x，公差为p时的最大差 int Max=0;for(int i=0;i<n;x+=p)Max=max(Max,abs(a[i++]-x));return Max;
}
int find(int p){int Max=-0x7fffffff,Min=0x7fffffff;for(int i=0,x=0;i<n;x+=p)Max=max(Max,a[i]-x),Min=min(Min,a[i++]-x);//cout<<p<<"->"<<(Max+Min>>1)<<endl;return Max+Min>>1;
}
int main(){freopen("bun.in","r",stdin);freopen("bun.out","w",stdout);n=in();for(int i=0;i<n;++i)a[i]=in();sort(a,a+n);bool flag=1;int MAXP=ceil(4E6/(n-1)),ans=0x7fffffff,ansp;for(int p=0;p<=MAXP;++p)if(cal(find(p),p)<ans)ans=cal(find(p),p),ansp=p;printf("%d\n%d %d\n",ans,find(ansp),ansp);
}