[ZOJ3334 Body Check]GXX神牛的美妙解法：解不等式

【题目大意】
给定n个工作，m条通道。
然后这m条通道要么全部一起完成工作，要么只有1条在完成工作，求把n个工作全部做完至少需要多长时间。
【算法分析】
http://hi.baidu.com/pojoflcc/blog/item/a5e757816511ccdb9123d9b4.html
Lcc大神也写了解题报告，但是他的方法思路过于繁杂。。。虽然也可以做到排序的复杂度。
实际上，我们就是要让n个工作的并行时间尽可能地长。

姑且设这个并行时间为ans。
本题容易得到一个二分ans的算法。
具体是：
先二分ans。
然后将大于ans的工作时间置为ans。最后判定所有工作时间的和是否>=ans*m
是，则可行，否则不可行。
（想象你在填一个m*ans的表，就很容易理解）

然后现在根据GXX神牛的指示。
实际上不需要二分答案。

我们现在来看。假设我们将工作时间Ai已经按降序排列。
并再次假设A[i]<=ans<=A[i+1]
那么类似二分的判定的地方得到一个不等式
S[i+1,n]+i*ans>=m*ans     （S[i,j]表示从a[i]到a[j]的和）
于是我们整理一下，得出3个不等式：
ans>=A[i]           ——————①
ans<=A[i+1]       ——————②
ans<=S/(m-i)     ——————③
然后解它们看在这个区间有无解就行了。
可能大家觉得第③式有点问题。就是那个(m-i)的正负不知道，所以不等式不知道要不要变号。
实际上，在i递增到m=i时，必然就有解，所以不会出现m于是问题得到完美解决。
【时间复杂度】排序O(n lg n)+处理O(n)
【空间复杂度】O(n)
【其它】
1、深深地YM GXX神牛
2、注意到那个二分的解法，本题精度要求是1e-9，所以很容易挂。。。当然也是有可能AC的。
【CODE】
#include #include #include #define AA (*((double*)A))
#define BB (*((double*)B))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=1005;
int m,n;
double a[N],s[N],ans,x;

void solve(){
ans=0;
a[n+1]=s[n+1]=0;
a[0]=1e20;
for (int i=n;i>=1;i–) s[i]=s[i+1]+a[i];
for (int i=0;i<=n;i++)
if (i==m){
ans=a[i];
break;
}else
if (m>i){
x=min(a[i],s[i+1]/(m-i));
if (x>=a[i+1]){
ans=x;
break;
}
}
printf("%.9lfn",s[1]-ans*m+ans);
}

int cmp(const void *A,const void *B){
if (AA if (AA>BB) return -1;
return 0;
}

int main(){
while (scanf("%d%d",&m,&n)!=EOF){
for (int i=1;i<=n;i++) scanf("%lf",&a[i]);
qsort(a+1,n,sizeof(double),cmp);
solve();
}
}