📐分数规划问题📐

问题描述：
给定两个长度为 n 的数组：

价值数组 a[]（即美味度）
成本数组 b[]（即时间消耗）
要求选择恰好 s 个元素，使得选中的元素满足：
最大化 $\frac{\sum_{i \in S} a_{i}}{\sum_{i \in S} b_{i}}$

T=a1+a2+a3…+ai/b1+b2+b3+....+bi的最值

//化简一下
//设最大值为x即x=a1+a2+a3…+ai/b1+b2+b3+....+bi
//T=(a1-b1x)+(a2-b2x)+(a3-b3x)+…+(ai-bix)=0
//
//我们设一个变量z，如果z==x（最大值）为标准答案
//如果z[HTML_REMOVED]0 如果z>x则T<0 这里单调性就出来了！

思路就很明显了,设定一个[L,R]
L明显取0 R可以取MAX(ai)，每次用二分逼近答案。

check函数的思路就是，求出每一项的(ai-bi*x)排序找到最大k项—这里有一个贪心思路。

即只要最大k项(a1-b1*x)的和满足<0就肯定不行，相反>0就肯定存在。

测试链接https://www.luogu.com.cn/problem/P1570

附上代码:
typedef struct {
double a;
double b;
}data;

int Max(int k1,int k2){
return(k1>k2)?k1:k2;
}
int compare(const void a, const void b) {
double aa = (double)a;
double bb = (double)b;
if (aa > bb) return -1;
if (aa < bb) return 1;
return 0;
}

bool check(double x, data d, int size, int k) {
double r = (double*)malloc(size * sizeof(double));
for (int i = 0; i < size; i++) {
r[i] = d[i].a - x * d[i].b;
}

qsort(r, size, sizeof(double), compare);

double sum = 0.0;
for (int i = 0; i < k; i++) {
    sum += r[i];
}

return (sum >= 0)?true:false;

}
double binary(data* d, int size, double l, double r, int k) {
double small = 0.000001;

double ans = 0.0;
while (l <= r && r - l >= small) {
    double mid = (l + r) / 2;
    if (check(mid, d, size, k)) {
        ans = mid;
        l = mid + small;
    }
    else {
        r = mid - small;
    }
}
return ans;

}

int main() {
int k, n;
scanf(“%d %d”, &n, &k);

data d[10010];

for (int i = 0; i < n; i++) {
    scanf("%lf",&d[i].a);
}

for(int i=0;i<n;i++){
    scanf("%lf",&d[i].b);
}

double right = 0;
for (int i = 0; i < n; i++) {
    right = Max(right, d[i].a);
}

double ans = binary(d, n, 0, right, k);

printf("%.3f", ans);
return 0;

}