K Best poj 3111 (01分数规划---二分搜索)
题目：http://poj.org/problem?id=3111
思路：给定n个二元组（v,w）保留k个，使得 sigma(v)/sigma(w)的值最大：
代码：
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<vector>using namespace std;const int Maxn=100001;const double eps=1e-8;struct node{int w,v,index;double r;};node sn[Maxn];int n,k;bool cmp(node x,node y){return x.r>y.r;}bool can(double mid){for(int i=0;i<n;i++){sn[i].r=sn[i].v-mid*sn[i].w;}//sort(sn,sn+n,cmp);partial_sort(sn,sn+k,sn+n,cmp);double sum=0;for(int i=0;i<k;i++){sum+=sn[i].r;}return sum>=0;}int main(){while(cin>>n>>k){int sum=0;for(int i=0;i<n;i++){scanf("%d %d",&sn[i].v,&sn[i].w);sn[i].index=i+1;sum+=sn[i].v;}double lb=0.0,ub=sum*1.0;while(fabs(ub-lb)>eps){double mid=(lb+ub)/2;if(can(mid)) lb=mid;else ub=mid;}for(int i=0;i<k-1;i++){cout<<sn[i].index<<" ";}cout<<sn[k-1].index<<endl;}return 0;}