问题：需求
有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$ 算出来，排序得出答案即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #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;
}
|
实践：题目
