问题：需求

有n对元素 $(𝑣_1,𝑤_1),(𝑣_2,𝑤_2), (𝑣_3,𝑤_3), …,(𝑣_𝑛,𝑤_𝑛)$。要求从中挑选出 $k$ 对，使得 $v$ 的和除以 $w$ 的和最大。

解法：分析

显然是一道二分题，我们直接二分最大值可得式子：（ $x[i]$ 表示选或不选，值是 $0$ 或 $1$ ）

$\cfrac{\sum\limits_{i=1}^n{v_i\times x_i}}{\sum\limits_{i=1}^n{w_i\times x_i}} >mid$

由于浮点精度误差问题，将其改写为乘法形式

$\sum\limits_{i=1}^n{(v_i\times x_i)}>mid \times \sum\limits_{i=1}^n{(w_i\times x_i)}$

接着移项

$\sum\limits_{i=1}^n{(v_i\times x_i)}-mid \times \sum\limits_{i=1}^n{(w_i\times x_i)} > 0$

由于有 $x_i$ 的共因子，所以提取出来

$\sum\limits_{i=1}^n{w_i(v_i-mid\times w_i)} > 0$

最后只需要把每一个 $v_i - mid\times w_i$ 算出来，排序得出答案即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-8;

int n, k;
int v[100010], w[100010];
int vis[100010];

void Input(){
	scanf("%d%d", &n, &k);
	for(int i=1; i<=n; i++){
		scanf("%d%d", &v[i], &w[i]);
	}
}

bool cmp(pair<double , int >&a, pair<double , int >&b){
	return a.first>b.first;
}

bool Check(double mid){
	vector<pair<double , int > >a;
	for(int i=1; i<=n; i++){
		a.push_back(make_pair(v[i]-w[i]*mid, i));
	}
	sort(a.begin(), a.end(), cmp);
	double sum=0;
	for(int i=0; i<k; i++){
		sum+=a[i].first;
	}
	if(sum>-eps){
		for(int i=1; i<=n; i++){
			vis[i]=0;
		}
		for(int i=0; i<k; i++){
			vis[a[i].second]=1;
		}
		return 1;
	}
	return 0;
}

void Work(){
	double l=0, r=10000010;
	while(fabs(l-r)>eps){
		double mid=(l+r)/2;
		if(Check(mid)){
			l=mid;
		}else{
			r=mid;
		}
	}
	for(int i=1; i<=n; i++){
		if(vis[i]){
			printf("%d ", i);
		}
	}
}

int main(){
	Input();
	Work();
	return 0;
}