n个物品重量价值分别为wi,vi；取k个值使得单位重量的价值最大。 输入： n k 接下来n行表示重量 接下来n行表示价值
分析： 贪心是错的。 使的vi/wi最大 ，，假设单位重量的最大价值为x。 则vi /wi >=x 即vi-wi*x>=0 所以按照上面公式排序二分求解。
;const int MAXN = 1010;int n, k;struct node{double w;double v;}p[MAXN];double q[MAXN];bool cmp(double a, double b){return a > b;}bool c(double x){for (int i = 0; i < n; i++)q[i] = p[i].v – x*p[i].w;sort(q, q + n,cmp);double sum = 0;for (int i = 0; i < k; i++)sum += q[i];if (sum >= 0)return true;;}int main(){while (cin >> n>>k){for (int i = 0; i < n; i++)cin >> p[i].w;for (int i = 0; i < n; i++)cin >> p[i].v;double ans = 0;double down = 0, up = 1e9;for (int i = 0; i < 100; i++){double mid = (down + up) / 2;if (c(mid))down = mid;elseup = mid;}printf(“%.2lf\n”,up);}return 0;}
去陌生的街角，去做一切我们曾经或现在也很想做的事情，
