问题
有 $n$ 个物品，每个物品有两个属性 $a_i$ 和 $b_i$，需要选出 $k$ 个，设选出的编号集合是 $S$。
最大化
$$\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}$$
保留一定精度。
二分
这个问题是可以二分的，考虑二分一个答案 $ans$，条件是
$$\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i} \ge ans$$
可以转化为
$$\sum_{i\in S} a_i-ans \sum_{i\in S} b_i \ge 0$$
这样只需要按照 $a_i-ans*b_i$ 排序取最大的 $k$ 个判断即可。
直接使用 sort()，令 $w$ 表示 $\frac{\text{值域}}{\text{精度}}$，复杂度 $O(n\log n\log w)$。
用 nth_element()，复杂度 $O(n\log w)$。
问题有其他变种，大概挺simple，二分基本上就好了。
迭代
不知道这复杂度对不对，好像正确性也不知道，反正跑得快。
先令 $ans=0$，每次用相同的方法，可以求出一个 $\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}$，显然这也是一个合法的答案，并且肯定更优。
一直迭代直到增加量很小时结束。
例题
LOJ #149. 01分数规划
模板
迭代目前跑得最快。
二分的代码的写法大概是因为寻址不连续，没有写 struct 一起 nth_element() 快。
代码
二分
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
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int N = 100005;
int n, k, a[N], b[N], g[N];
double f[N];
inline bool cmp(int x, int y){ return f[x]>f[y];}
inline double check(double x){
for(int i=1; i<=n; ++i) f[i]=a[i]-b[i]*x, g[i]=i;
nth_element(g+1, g+k+1, g+n+1, cmp);
ll sa=0, sb=0;
for(int i=1; i<=k; ++i) sa+=a[g[i]], sb+=b[g[i]];
return (double)sa/sb;
}
int main() {
read(n), read(k);
for(int i=1; i<=n; ++i) read(a[i]);
for(int i=1; i<=n; ++i) read(b[i]);
double l=0, r=1e6, ans=0;
while(r-l>1e-7){
double mid=(l+r)/2;
if(check(mid)>=mid) ans=mid, l=mid; else r=mid;
}
return printf("%.4f", ans), 0;
}
|
迭代
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
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int N = 100005;
int n, k;
struct item{
int a, b;
double f;
inline bool operator <(const item &rhs)const{ return f>rhs.f;}
} a[N];
inline double check(double x){
for(int i=1; i<=n; ++i) a[i].f=a[i].a-a[i].b*x;
nth_element(a+1, a+k+1, a+n+1);
ll sa=0, sb=0;
for(int i=1; i<=k; ++i) sa+=a[i].a, sb+=a[i].b;
return (double)sa/sb;
}
int main() {
read(n), read(k);
for(int i=1; i<=n; ++i) read(a[i].a);
for(int i=1; i<=n; ++i) read(a[i].b);
ll sa=0, sb=0;
for(int i=1; i<=k; ++i) sa+=a[i].a, sb+=a[i].b;
double ans=(double)sa/sb, last;
do ans=check(last=ans); while(ans-last>1e-6);
return printf("%.4f", ans), 0;
}
|