POJ-2976-Dropping tests（0/1分数规划）

题目链接：http://poj.org/problem?id=2976

题目大意：给出n次考试，每次考试都有 解决问题数Ai 和 问题总数两种Bi 属性。我们从中选择n-k场考试，使得最大。输出最大的答案（Ans）。

思路：0/1分数规划入门题：

二分Ans，前n-k项之和==0.

ACCode：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
  
#include<stdio.h>
#include<string.h> 
#include<math.h> 
#include<time.h>

#include<map>  
#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
#define ll long long 
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ??
//std::ios::sync_with_stdio(false);
//  register 
const int MAXN=1e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;

double A[MAXN],B[MAXN],Sum[MAXN];
int n,k;

int Judge(double mid){
	for(int i=1;i<=n;++i){
		Sum[i]=A[i]-mid*B[i];
	}sort(Sum+1,Sum+1+n);
	double res=0.0;
	for(int i=1+k;i<=n;++i){
		res+=Sum[i];
	}
	if(res>0) return 1;
	else return 0;
}
int main(){
	while(~scanf("%d%d",&n,&k)){
		if(n==0&&k==0) break;
		for(int i=1;i<=n;++i) scanf("%lf",&A[i]);
		for(int i=1;i<=n;++i) scanf("%lf",&B[i]);
		double l=0.0,r=1.0,mid,ans;
		while(l<r-EPS){
//			cout<<l<<" " <<r<<endl;
			mid=(l+r)/2.0;
			if(Judge(mid)) ans=mid,l=mid;
			else r=mid;
		}
		printf("%.0f\n",100.0*(l+r)/2.0);
	}
}