Ryan_<

二分法：

程序框架：

L:=...;R:=...;
Repeat
  Mid:=(L+R)/2;
  For I=1..X do D[i]:=A[i]-Mid*B[i];//根据Mid计算D数组
  if 检查（Mid）成功 then L:=Mid else R:=Mid；

Until abs(L-R)<Eps;    

Dinkelbach算法：

程序框架：

L:=随便什么东西;
Repeat
  Ans:=L;
  For I=1..X do D[i]:=A[i]-L*B[i];//根据L计算D数组
  根据具体情况检查解并记录;
  p:=0;q:=0;
  for I=每一个元素 do 
     如果元素I在解中
        begin
          p:=p+A[i];q:=q+A[i];
        end;
  L:=p/q;//更新解
Until abs(Ans-L)<Eps;  

题目：

POJ 2976 Dropping tests

给定n个二元组(a,b)，删除k个二元组，使得剩下的a元素之和与b元素之和的比率最大（比率最后乘100输出)

01分数规划的基本模型

具体分析过程见笔记/ http://www.cnblogs.com/proverbs/archive/2013/01/09/2853725.html

注意：
1、二分答案m是非严格的，这样便于判断
2、bi应当不全为0,才有意义
3、要求sigma((ai-bi*P)*xi)的最大值,可以运用贪心的思想,从大到小排序
 
对于本题来说：0 ≤ ai ≤ bi ,可以确定m的范围为[0,1]。

不太懂这句话：

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

难道是说精度要求不高?

#define eps 1e-8
typedef double DB;
const int N=1000+10;
int n,K;DB l,r,mid;
struct data{
	DB a,b,c;
	bool operator <(const data &rhs)const{
		return c>rhs.c;
	}
}x[N];
bool check(DB mid)
{
	DB res=0.0;
	F(i,1,n) x[i].c=x[i].a-x[i].b*mid;
	sort(x+1,x+n+1); 
	F(i,1,n-K) res+=x[i].c;
	if(res<=0.0) return true; 
	else return false;
}	
int main()
{
	while(scanf("%d%d",&n,&K)==2 && (n||K)){//注意判断条件 
		F(i,1,n) scanf("%lf",&x[i].a);
		F(i,1,n) scanf("%lf",&x[i].b);
		DB l=0.0,r=1.0;
		while(fabs(r-l)>eps){
			DB mid=(l+r)/2.0;
			if(check(mid)) r=mid;
			else l=mid;
		}
		printf("%.0lf\n",l*100);
	}
	return 0;
}